use crate::attr::{
AttrSelectorOperation, AttrSelectorWithOptionalNamespace, CaseSensitivity, NamespaceConstraint,
ParsedAttrSelectorOperation, ParsedCaseSensitivity,
};
use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
use crate::parser::{
AncestorHashes, Combinator, Component, LocalName, NthSelectorData, RelativeSelectorMatchHint,
};
use crate::parser::{
NonTSPseudoClass, RelativeSelector, Selector, SelectorImpl, SelectorIter, SelectorList,
};
use crate::tree::Element;
use smallvec::SmallVec;
use std::borrow::Borrow;
pub use crate::context::*;
pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
bitflags! {
#[derive(Clone, Copy)]
pub struct ElementSelectorFlags: usize {
const HAS_SLOW_SELECTOR = 1 << 0;
const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1;
const HAS_SLOW_SELECTOR_NTH_OF = 1 << 2;
const HAS_EDGE_CHILD_SELECTOR = 1 << 3;
const HAS_EMPTY_SELECTOR = 1 << 4;
}
}
impl ElementSelectorFlags {
pub fn for_self(self) -> ElementSelectorFlags {
self & ElementSelectorFlags::HAS_EMPTY_SELECTOR
}
pub fn for_parent(self) -> ElementSelectorFlags {
self & (ElementSelectorFlags::HAS_SLOW_SELECTOR |
ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS |
ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF |
ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR)
}
}
struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
shared: &'a mut MatchingContext<'b, Impl>,
quirks_data: Option<(Rightmost, SelectorIter<'a, Impl>)>,
}
#[inline(always)]
pub fn matches_selector_list<E>(
selector_list: &SelectorList<E::Impl>,
element: &E,
context: &mut MatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
for selector in &selector_list.0 {
let matches = matches_selector(selector, 0, None, element, context);
if matches {
return true;
}
}
false
}
#[inline(always)]
fn may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool {
for i in 0..3 {
let packed = hashes.packed_hashes[i];
if packed == 0 {
return true;
}
if !bf.might_contain_hash(packed & BLOOM_HASH_MASK) {
return false;
}
}
let fourth = hashes.fourth_hash();
fourth == 0 || bf.might_contain_hash(fourth)
}
#[derive(Clone, Copy, Eq, PartialEq)]
enum SelectorMatchingResult {
Matched,
NotMatchedAndRestartFromClosestLaterSibling,
NotMatchedAndRestartFromClosestDescendant,
NotMatchedGlobally,
}
#[inline(always)]
pub fn matches_selector<E>(
selector: &Selector<E::Impl>,
offset: usize,
hashes: Option<&AncestorHashes>,
element: &E,
context: &mut MatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
if let Some(hashes) = hashes {
if let Some(filter) = context.bloom_filter {
if !may_match(hashes, filter) {
return false;
}
}
}
matches_complex_selector(selector.iter_from(offset), element, context)
}
pub enum CompoundSelectorMatchingResult {
FullyMatched,
Matched { next_combinator_offset: usize },
NotMatched,
}
pub fn matches_compound_selector_from<E>(
selector: &Selector<E::Impl>,
mut from_offset: usize,
context: &mut MatchingContext<E::Impl>,
element: &E,
) -> CompoundSelectorMatchingResult
where
E: Element,
{
if cfg!(debug_assertions) && from_offset != 0 {
selector.combinator_at_parse_order(from_offset - 1); }
let mut local_context = LocalMatchingContext {
shared: context,
quirks_data: None,
};
let start_offset = from_offset;
for component in selector.iter_raw_parse_order_from(from_offset) {
if matches!(*component, Component::Combinator(..)) {
debug_assert_ne!(from_offset, 0, "Selector started with a combinator?");
break;
}
from_offset += 1;
}
debug_assert!(from_offset >= 1);
debug_assert!(from_offset <= selector.len());
let iter = selector.iter_from(selector.len() - from_offset);
debug_assert!(
iter.clone().next().is_some() ||
(from_offset != selector.len() &&
matches!(
selector.combinator_at_parse_order(from_offset),
Combinator::SlotAssignment | Combinator::PseudoElement
)),
"Got the math wrong: {:?} | {:?} | {} {}",
selector,
selector.iter_raw_match_order().as_slice(),
from_offset,
start_offset
);
for component in iter {
if !matches_simple_selector(component, element, &mut local_context) {
return CompoundSelectorMatchingResult::NotMatched;
}
}
if from_offset != selector.len() {
return CompoundSelectorMatchingResult::Matched {
next_combinator_offset: from_offset,
};
}
CompoundSelectorMatchingResult::FullyMatched
}
#[inline(always)]
pub fn matches_complex_selector<E>(
mut iter: SelectorIter<E::Impl>,
element: &E,
context: &mut MatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
if context.matching_mode() == MatchingMode::ForStatelessPseudoElement && !context.is_nested() {
match *iter.next().unwrap() {
Component::PseudoElement(ref pseudo) => {
if let Some(ref f) = context.pseudo_element_matching_fn {
if !f(pseudo) {
return false;
}
}
},
ref other => {
debug_assert!(
false,
"Used MatchingMode::ForStatelessPseudoElement \
in a non-pseudo selector {:?}",
other
);
return false;
},
}
if !iter.matches_for_stateless_pseudo_element() {
return false;
}
let next_sequence = iter.next_sequence().unwrap();
debug_assert_eq!(next_sequence, Combinator::PseudoElement);
}
let result = matches_complex_selector_internal(iter, element, context, Rightmost::Yes);
matches!(result, SelectorMatchingResult::Matched)
}
fn matches_complex_selector_list<E: Element>(
list: &[Selector<E::Impl>],
element: &E,
context: &mut MatchingContext<E::Impl>,
) -> bool {
for selector in list {
if matches_complex_selector(selector.iter(), element, context) {
return true;
}
}
false
}
fn matches_relative_selectors<E: Element>(
selectors: &[RelativeSelector<E::Impl>],
element: &E,
context: &mut MatchingContext<E::Impl>,
) -> bool {
context.considered_relative_selector = RelativeSelectorMatchingState::ConsideredAnchor;
for RelativeSelector {
match_hint,
selector,
} in selectors.iter()
{
let (traverse_subtree, traverse_siblings, mut next_element) = match match_hint {
RelativeSelectorMatchHint::InChild => (false, true, element.first_element_child()),
RelativeSelectorMatchHint::InSubtree => (true, true, element.first_element_child()),
RelativeSelectorMatchHint::InSibling => (false, true, element.next_sibling_element()),
RelativeSelectorMatchHint::InSiblingSubtree => {
(true, true, element.next_sibling_element())
},
RelativeSelectorMatchHint::InNextSibling => {
(false, false, element.next_sibling_element())
},
RelativeSelectorMatchHint::InNextSiblingSubtree => {
(true, false, element.next_sibling_element())
},
};
while let Some(el) = next_element {
if matches_complex_selector(selector.iter(), &el, context) {
return true;
}
if traverse_subtree && matches_relative_selector_subtree(selector, &el, context) {
return true;
}
if !traverse_siblings {
break;
}
next_element = el.next_sibling_element();
}
}
false
}
fn matches_relative_selector_subtree<E: Element>(
selector: &Selector<E::Impl>,
element: &E,
context: &mut MatchingContext<E::Impl>,
) -> bool {
let mut current = element.first_element_child();
while let Some(el) = current {
if matches_complex_selector(selector.iter(), &el, context) {
return true;
}
if matches_relative_selector_subtree(selector, &el, context) {
return true;
}
current = el.next_sibling_element();
}
false
}
fn hover_and_active_quirk_applies<Impl: SelectorImpl>(
selector_iter: &SelectorIter<Impl>,
context: &MatchingContext<Impl>,
rightmost: Rightmost,
) -> bool {
if context.quirks_mode() != QuirksMode::Quirks {
return false;
}
if context.is_nested() {
return false;
}
if rightmost == Rightmost::Yes &&
context.matching_mode() == MatchingMode::ForStatelessPseudoElement
{
return false;
}
selector_iter.clone().all(|simple| match *simple {
Component::LocalName(_) |
Component::AttributeInNoNamespaceExists { .. } |
Component::AttributeInNoNamespace { .. } |
Component::AttributeOther(_) |
Component::ID(_) |
Component::Class(_) |
Component::PseudoElement(_) |
Component::Negation(_) |
Component::Empty |
Component::Nth(_) |
Component::NthOf(_) => false,
Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
_ => true,
})
}
#[derive(Clone, Copy, PartialEq)]
enum Rightmost {
Yes,
No,
}
#[inline(always)]
fn next_element_for_combinator<E>(
element: &E,
combinator: Combinator,
selector: &SelectorIter<E::Impl>,
context: &MatchingContext<E::Impl>,
) -> Option<E>
where
E: Element,
{
match combinator {
Combinator::NextSibling | Combinator::LaterSibling => element.prev_sibling_element(),
Combinator::Child | Combinator::Descendant => {
match element.parent_element() {
Some(e) => return Some(e),
None => {},
}
if !element.parent_node_is_shadow_root() {
return None;
}
if !selector.clone().is_featureless_host_selector() {
return None;
}
element.containing_shadow_host()
},
Combinator::Part => element.containing_shadow_host(),
Combinator::SlotAssignment => {
debug_assert!(element
.assigned_slot()
.map_or(true, |s| s.is_html_slot_element()));
let scope = context.current_host?;
let mut current_slot = element.assigned_slot()?;
while current_slot.containing_shadow_host().unwrap().opaque() != scope {
current_slot = current_slot.assigned_slot()?;
}
Some(current_slot)
},
Combinator::PseudoElement => element.pseudo_element_originating_element(),
}
}
fn matches_complex_selector_internal<E>(
mut selector_iter: SelectorIter<E::Impl>,
element: &E,
context: &mut MatchingContext<E::Impl>,
rightmost: Rightmost,
) -> SelectorMatchingResult
where
E: Element,
{
debug!(
"Matching complex selector {:?} for {:?}",
selector_iter, element
);
let matches_compound_selector =
matches_compound_selector(&mut selector_iter, element, context, rightmost);
let combinator = selector_iter.next_sequence();
if combinator.map_or(false, |c| c.is_sibling()) {
if context.needs_selector_flags() {
element.apply_selector_flags(ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS);
}
}
if !matches_compound_selector {
return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
}
let combinator = match combinator {
None => return SelectorMatchingResult::Matched,
Some(c) => c,
};
let candidate_not_found = match combinator {
Combinator::NextSibling | Combinator::LaterSibling => {
SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
},
Combinator::Child |
Combinator::Descendant |
Combinator::SlotAssignment |
Combinator::Part |
Combinator::PseudoElement => SelectorMatchingResult::NotMatchedGlobally,
};
let mut visited_handling = if combinator.is_sibling() {
VisitedHandlingMode::AllLinksUnvisited
} else {
context.visited_handling()
};
let mut element = element.clone();
loop {
if element.is_link() {
visited_handling = VisitedHandlingMode::AllLinksUnvisited;
}
element = match next_element_for_combinator(&element, combinator, &selector_iter, &context)
{
None => return candidate_not_found,
Some(next_element) => next_element,
};
let result = context.with_visited_handling_mode(visited_handling, |context| {
matches_complex_selector_internal(
selector_iter.clone(),
&element,
context,
Rightmost::No,
)
});
match (result, combinator) {
(SelectorMatchingResult::Matched, _) |
(SelectorMatchingResult::NotMatchedGlobally, _) |
(_, Combinator::NextSibling) => {
return result;
},
(_, Combinator::PseudoElement) | (_, Combinator::Child) => {
return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant;
},
(
SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
Combinator::LaterSibling,
) => {
return result;
},
_ => {},
}
}
}
#[inline]
fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
where
E: Element,
{
let name = select_name(element, &local_name.name, &local_name.lower_name).borrow();
element.has_local_name(name)
}
fn matches_part<E>(
element: &E,
parts: &[<E::Impl as SelectorImpl>::Identifier],
context: &mut MatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
let mut hosts = SmallVec::<[E; 4]>::new();
let mut host = match element.containing_shadow_host() {
Some(h) => h,
None => return false,
};
let current_host = context.current_host;
if current_host != Some(host.opaque()) {
loop {
let outer_host = host.containing_shadow_host();
if outer_host.as_ref().map(|h| h.opaque()) == current_host {
break;
}
let outer_host = match outer_host {
Some(h) => h,
None => return false,
};
hosts.push(host);
host = outer_host;
}
}
parts.iter().all(|part| {
let mut part = part.clone();
for host in hosts.iter().rev() {
part = match host.imported_part(&part) {
Some(p) => p,
None => return false,
};
}
element.is_part(&part)
})
}
fn matches_host<E>(
element: &E,
selector: Option<&Selector<E::Impl>>,
context: &mut MatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
let host = match context.shadow_host() {
Some(h) => h,
None => return false,
};
if host != element.opaque() {
return false;
}
selector.map_or(true, |selector| {
context.nest(|context| matches_complex_selector(selector.iter(), element, context))
})
}
fn matches_slotted<E>(
element: &E,
selector: &Selector<E::Impl>,
context: &mut MatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
if element.is_html_slot_element() {
return false;
}
context.nest(|context| matches_complex_selector(selector.iter(), element, context))
}
fn matches_rare_attribute_selector<E>(
element: &E,
attr_sel: &AttrSelectorWithOptionalNamespace<E::Impl>,
) -> bool
where
E: Element,
{
let empty_string;
let namespace = match attr_sel.namespace() {
Some(ns) => ns,
None => {
empty_string = crate::parser::namespace_empty_string::<E::Impl>();
NamespaceConstraint::Specific(&empty_string)
},
};
element.attr_matches(
&namespace,
select_name(element, &attr_sel.local_name, &attr_sel.local_name_lower),
&match attr_sel.operation {
ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
ParsedAttrSelectorOperation::WithValue {
operator,
case_sensitivity,
ref value,
} => AttrSelectorOperation::WithValue {
operator,
case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
value,
},
},
)
}
#[inline]
fn matches_compound_selector<E>(
selector_iter: &mut SelectorIter<E::Impl>,
element: &E,
context: &mut MatchingContext<E::Impl>,
rightmost: Rightmost,
) -> bool
where
E: Element,
{
let quirks_data = if context.quirks_mode() == QuirksMode::Quirks {
Some((rightmost, selector_iter.clone()))
} else {
None
};
let mut local_context = LocalMatchingContext {
shared: context,
quirks_data,
};
selector_iter.all(|simple| matches_simple_selector(simple, element, &mut local_context))
}
fn matches_simple_selector<E>(
selector: &Component<E::Impl>,
element: &E,
context: &mut LocalMatchingContext<E::Impl>,
) -> bool
where
E: Element,
{
debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
match *selector {
Component::ID(ref id) => {
element.has_id(id, context.shared.classes_and_ids_case_sensitivity())
},
Component::Class(ref class) => {
element.has_class(class, context.shared.classes_and_ids_case_sensitivity())
},
Component::LocalName(ref local_name) => matches_local_name(element, local_name),
Component::AttributeInNoNamespaceExists {
ref local_name,
ref local_name_lower,
} => element.has_attr_in_no_namespace(select_name(element, local_name, local_name_lower)),
Component::AttributeInNoNamespace {
ref local_name,
ref value,
operator,
case_sensitivity,
} => element.attr_matches(
&NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
local_name,
&AttrSelectorOperation::WithValue {
operator,
case_sensitivity: to_unconditional_case_sensitivity(case_sensitivity, element),
value,
},
),
Component::AttributeOther(ref attr_sel) => {
matches_rare_attribute_selector(element, attr_sel)
},
Component::Part(ref parts) => matches_part(element, parts, &mut context.shared),
Component::Slotted(ref selector) => matches_slotted(element, selector, &mut context.shared),
Component::PseudoElement(ref pseudo) => {
element.match_pseudo_element(pseudo, context.shared)
},
Component::ExplicitUniversalType | Component::ExplicitAnyNamespace => true,
Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
element.has_namespace(&url.borrow())
},
Component::ExplicitNoNamespace => {
let ns = crate::parser::namespace_empty_string::<E::Impl>();
element.has_namespace(&ns.borrow())
},
Component::NonTSPseudoClass(ref pc) => {
if let Some((ref rightmost, ref iter)) = context.quirks_data {
if pc.is_active_or_hover() &&
!element.is_link() &&
hover_and_active_quirk_applies(iter, context.shared, *rightmost)
{
return false;
}
}
element.match_non_ts_pseudo_class(pc, &mut context.shared)
},
Component::Root => element.is_root(),
Component::Empty => {
if context.shared.needs_selector_flags() {
element.apply_selector_flags(ElementSelectorFlags::HAS_EMPTY_SELECTOR);
}
element.is_empty()
},
Component::Host(ref selector) => {
matches_host(element, selector.as_ref(), &mut context.shared)
},
Component::ParentSelector |
Component::Scope => match context.shared.scope_element {
Some(ref scope_element) => element.opaque() == *scope_element,
None => element.is_root(),
},
Component::Nth(ref nth_data) => {
matches_generic_nth_child(element, context.shared, nth_data, &[])
},
Component::NthOf(ref nth_of_data) => context.shared.nest(|context| {
matches_generic_nth_child(
element,
context,
nth_of_data.nth_data(),
nth_of_data.selectors(),
)
}),
Component::Is(ref list) | Component::Where(ref list) => context
.shared
.nest(|context| matches_complex_selector_list(list, element, context)),
Component::Negation(ref list) => context
.shared
.nest_for_negation(|context| !matches_complex_selector_list(list, element, context)),
Component::Has(ref relative_selectors) => context
.shared
.nest_for_relative_selector(element.opaque(), |context| {
matches_relative_selectors(relative_selectors, element, context)
}),
Component::Combinator(_) => unsafe {
debug_unreachable!("Shouldn't try to selector-match combinators")
},
Component::RelativeSelectorAnchor => {
let anchor = context.shared.relative_selector_anchor();
debug_assert!(
anchor.is_some(),
"Relative selector outside of relative selector matching?"
);
anchor.map_or(false, |a| a == element.opaque())
},
}
}
#[inline(always)]
fn select_name<'a, E: Element, T: PartialEq>(
element: &E,
local_name: &'a T,
local_name_lower: &'a T,
) -> &'a T {
if local_name == local_name_lower || element.is_html_element_in_html_document() {
local_name_lower
} else {
local_name
}
}
#[inline(always)]
fn to_unconditional_case_sensitivity<'a, E: Element>(
parsed: ParsedCaseSensitivity,
element: &E,
) -> CaseSensitivity {
match parsed {
ParsedCaseSensitivity::CaseSensitive | ParsedCaseSensitivity::ExplicitCaseSensitive => {
CaseSensitivity::CaseSensitive
},
ParsedCaseSensitivity::AsciiCaseInsensitive => CaseSensitivity::AsciiCaseInsensitive,
ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {
if element.is_html_element_in_html_document() {
CaseSensitivity::AsciiCaseInsensitive
} else {
CaseSensitivity::CaseSensitive
}
},
}
}
fn matches_generic_nth_child<E>(
element: &E,
context: &mut MatchingContext<E::Impl>,
nth_data: &NthSelectorData,
selectors: &[Selector<E::Impl>],
) -> bool
where
E: Element,
{
if element.ignores_nth_child_selectors() {
return false;
}
let has_selectors = !selectors.is_empty();
let selectors_match =
!has_selectors || matches_complex_selector_list(selectors, element, context);
if context.ignores_nth_child_selectors_for_invalidation() {
return selectors_match && !context.in_negation();
}
let NthSelectorData { ty, a, b, .. } = *nth_data;
let is_of_type = ty.is_of_type();
if ty.is_only() {
debug_assert!(
!has_selectors,
":only-child and :only-of-type cannot have a selector list!"
);
return matches_generic_nth_child(
element,
context,
&NthSelectorData::first(is_of_type),
selectors,
) && matches_generic_nth_child(
element,
context,
&NthSelectorData::last(is_of_type),
selectors,
);
}
let is_from_end = ty.is_from_end();
let is_edge_child_selector = a == 0 && b == 1 && !is_of_type && !has_selectors;
if context.needs_selector_flags() {
let mut flags = if is_edge_child_selector {
ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR
} else if is_from_end {
ElementSelectorFlags::HAS_SLOW_SELECTOR
} else {
ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
};
if has_selectors {
flags |= ElementSelectorFlags::HAS_SLOW_SELECTOR_NTH_OF;
}
element.apply_selector_flags(flags);
}
if !selectors_match {
return false;
}
if is_edge_child_selector {
return if is_from_end {
element.next_sibling_element()
} else {
element.prev_sibling_element()
}
.is_none();
}
let index = if let Some(i) = context
.nth_index_cache(is_of_type, is_from_end, selectors)
.lookup(element.opaque())
{
i
} else {
let i = nth_child_index(
element,
context,
selectors,
is_of_type,
is_from_end,
true,
);
context
.nth_index_cache(is_of_type, is_from_end, selectors)
.insert(element.opaque(), i);
i
};
debug_assert_eq!(
index,
nth_child_index(
element,
context,
selectors,
is_of_type,
is_from_end,
false
),
"invalid cache"
);
match index.checked_sub(b) {
None => false,
Some(an) => match an.checked_div(a) {
Some(n) => n >= 0 && a * n == an,
None => an == 0,
},
}
}
#[inline]
fn nth_child_index<E>(
element: &E,
context: &mut MatchingContext<E::Impl>,
selectors: &[Selector<E::Impl>],
is_of_type: bool,
is_from_end: bool,
check_cache: bool,
) -> i32
where
E: Element,
{
if check_cache &&
is_from_end &&
!context
.nth_index_cache(is_of_type, is_from_end, selectors)
.is_empty()
{
let mut index: i32 = 1;
let mut curr = element.clone();
while let Some(e) = curr.prev_sibling_element() {
curr = e;
let matches = if is_of_type {
element.is_same_type(&curr)
} else if !selectors.is_empty() {
matches_complex_selector_list(selectors, &curr, context)
} else {
true
};
if !matches {
continue;
}
if let Some(i) = context
.nth_index_cache(is_of_type, is_from_end, selectors)
.lookup(curr.opaque())
{
return i - index;
}
index += 1;
}
}
let mut index: i32 = 1;
let mut curr = element.clone();
let next = |e: E| {
if is_from_end {
e.next_sibling_element()
} else {
e.prev_sibling_element()
}
};
while let Some(e) = next(curr) {
curr = e;
let matches = if is_of_type {
element.is_same_type(&curr)
} else if !selectors.is_empty() {
matches_complex_selector_list(selectors, &curr, context)
} else {
true
};
if !matches {
continue;
}
if !is_from_end && check_cache {
if let Some(i) = context
.nth_index_cache(is_of_type, is_from_end, selectors)
.lookup(curr.opaque())
{
return i + index;
}
}
index += 1;
}
index
}