Bug Tracker

Opened 6 years ago

Closed 5 years ago

#14960 closed bug (migrated)

contents and children selectors can return elements out of order

Reported by: npben Owned by: gibson042
Priority: high Milestone: 1.12/2.2
Component: traversing Version: 1.11.0
Keywords: Cc:
Blocked by: Blocking:

Description

This problem exists in version 1.11.0.

I looked into source since the children and content selectors are just hardcoded not go into the logic that verifies uniqueness, it is probably just a situation that wasn't considered.

Examples are here for children() and here for contents().

Removing these two tags from the guaranteedunique array fixes the issue, but I didn't make a patch because I'm not familiar with the source and there may be a better way to handle it.

Workaround: calling $().add(unorderedobject) causes the uniqueness check to sort the elements.

Change History (7)

comment:1 Changed 6 years ago by scottgonzalez

Status: newopen

The uniqueness check doesn't run for children because we assume that the elements are already in order, so getting children will always result in an ordered set. But you've shown a scenario where that assumption is incorrect: A set containing a descendant of another element in the set.

comment:2 Changed 6 years ago by scottgonzalez

Component: unfiledtraversing

The uniqueness check was removed due to #7964.

comment:3 Changed 6 years ago by dmethvin

Milestone: None1.12/2.2
Priority: undecidedhigh

We can still avoid the uniqueness overhead for single-element sets as we currently do, but it seems like the whole optimization added in #7964 for multi-element sets may have to be backed out if there is no way to recognize this case.

comment:4 Changed 6 years ago by dmethvin

This test case shows it a little more clearly on the console: http://jsfiddle.net/sfMr2/7/

comment:5 Changed 6 years ago by reavowed

I've had a bit of a look at the problem and potential solutions, and figured I'd share my thoughts in case they're useful to anyone.

The problem is (as identified above) that while .children() and .contents() preserve uniqueness, they do not necessarily preserve ordering of a sequence, if that sequence contains nested elements.

Checking that a sequence contains no nested elements is probably costly, especially if you then further have to run $.unique over the children() anyway. However, under the assumption that the source sequence is ordered, there is a much more efficient way of checking / resorting. It uses the fact that if A < B, then A cannot be a descendant of B. Further, if A < B < C and B is not a descendant of A, then C cannot be a descendant of A either. So, the following algorithm will calculate the children of a sequence of elements while keeping the results ordered, in a single pass iteration:

  • Take the first element from the source sequence (call it A), and calculate its children.
  • Get more elements from the source sequence, for as long as they are descendants of A.
  • If no descendants were found, push the children of A to the result sequence.
  • If one or more descendants were found, push their children into an array with the children of A, run $.unique on this array, and push it to the result sequence.
  • Repeat with the next element in the sequence.

This should only run $.unique on those sets of child elements which we can't reasonably confirm are kept in order, while requiring at most (n-1) additional $.contains() calls. It's not a particularly complicated algorithm either, though I don't know enough about jQuery's NFRs to say whether it's worth adding as a special case, rather than the simpler solution of applying $.unique naively.

I would however definitely recommend renaming "guaranteedUnique" to something more specific like "preservesUniquenessAndOrder". It's a shame that jQuery.unique isn't named a bit more sensibly as well (Sizzle at least calls the function uniqueSort).

comment:6 Changed 5 years ago by gibson042

Owner: set to gibson042
Status: openassigned

comment:7 Changed 5 years ago by m_gol

Resolution: migrated
Status: assignedclosed
Note: See TracTickets for help on using tickets.