sorted(list(skipped_idx)) is redundant. The first thing sorted does is cast the iterable to a list.

(Assuming this function is kept - see my comment above where I have a version of this that operates on a list to start with).

Good catch.

I don't really care for this label stuff, but it's not part of the public interface, so we can just change it later, I suppose. So consider this comment to be me making cranky noises, not anything that needs action.

I guess this is switched over to being a set because of the _recombine_skipped algorithm below. I think it's not really necessary if we know that these skipped index lists are going to be sorted (maybe the idea is that that might change later with retrospective analysis?).

Here's a new algorithm for _recombine_skipped that takes a list instead of a set. My testing seems to indicate that it's about the same speed (actually it says it's maybe 8x faster than the set version, but that there's a huge disparity between the first and subsequent runs, indicating caching):

def _recombine_skipped(tokens, skipped_idxs):
    """
    >>> tokens = ["foo", " ", "bar", " ", "19June2000", "baz"]
    >>> skipped_idxs = set([0, 1, 2, 5])
    >>> _recombine_skipped(tokens, skipped_idxs)
    ["foo bar", "baz"]

    """
    # This groups consecutive values
    skipped_tokens = []
    idx_queue = []

    for idx in skipped_tokens:
        if idx_queue and idx - 1 != idx_queue[-1]:
            skipped_tokens.append(''.join(tokens[i] for i in idx_queue))
            idx_queue.clear()
        else:
            idx_queue.append(idx)

    if idx_queue:
        skipped_tokens.append(''.join(tokens[i] for i in idx_queue))

    return skipped_tokens

IIRC the main reason I used a set here was because of the if idx-1 in skipped_idxs check.

The secondary concern was idempotency. I think that eventually we're going to have to do multiple passes or look-backs or something.

The version you posted doesn't work for me. I'm assuming the for idx in skipped_tokens: is supposed to be for idx in skipped_idxs:. If I make that change, then in py3 I get ['foo bar'] and in py2 I get an AttributeError because there is no list.clear.

Ah, the version I had was indeed a bit off and not Python 2.7 compatible. Here's an updated version:

def _recombine_skipped_queue(tokens, skipped_idxs):
    """
    >>> tokens = ["foo", " ", "bar", " ", "19June2000", "baz"]
    >>> skipped_idxs = set([0, 1, 2, 5])
    >>> _recombine_skipped(tokens, skipped_idxs)
    ["foo bar", "baz"]

    """
    # This groups consecutive values
    skipped_tokens = []
    idx_queue = []
    for idx in skipped_idxs:
        if idx_queue and idx - 1 == [-1]:
        if len(idx_queue) and idx - 1 != idx_queue[-1]:
            skipped_tokens.append(''.join(map(tokens.__getitem__, idx_queue)))
            idx_queue = []

        idx_queue.append(idx)

    if idx_queue:
        skipped_tokens.append(''.join(map(tokens.__getitem__, idx_queue)))

    return skipped_tokens

Interestingly, I couldn't figure out why this was consistently slower than your version, since strings are immutable, I was expecting growing a string incrementally with + to be much slower than queuing up all the parts and combining them at the end, but lo and behold, if I switch over to using the += style method, the list version is faster than your version! I believe that's because in CPython they've special-cased this sort of string extension to try to extend the string in-place. See this StackOverflow question. Here's the faster version:

def _recombine_skipped(tokens, skipped_idxs):
    """
    >>> tokens = ["foo", " ", "bar", " ", "19June2000", "baz"]
    >>> skipped_idxs = set([0, 1, 2, 5])
    >>> _recombine_skipped(tokens, skipped_idxs)
    ["foo bar", "baz"]

    """
    # This groups consecutive values
    skipped_tokens = []
    idx_queue = []
    for i, idx in enumerate(skipped_idxs):
        if i > 0 and idx - 1 == skipped_idxs[i - 1]:
            skipped_tokens[-1] = skipped_tokens[-1] + tokens[idx]
        else:
            skipped_tokens.append(tokens[idx])

    return skipped_tokens

Despite the fact that this is not part of the Python spec, it seems that it's been implemented in Python 2.7 and 3.6 as well as pypy2 and pypy3. Using a loop that randomly generates token strings and skipped indices to test this:

Python 2.7:

$ python2.7 test_recombination_speed.py 
Running extend timing test
1000 loops, 500 sets: 0.884 ms per loop, 1.767 us per set
Running queue timing test
1000 loops, 500 sets: 1.263 ms per loop, 2.526 us per set
Running set timing test
1000 loops, 500 sets: 1.192 ms per loop, 2.384 us per set

Python 3.6:

$ python3.6 test_recombination_speed.py 
Running extend timing test
1000 loops, 500 sets: 1.075 ms per loop, 2.150 us per set
Running queue timing test
1000 loops, 500 sets: 1.469 ms per loop, 2.938 us per set
Running set timing test
1000 loops, 500 sets: 1.238 ms per loop, 2.477 us per set

pypy2:

$ pypy test_recombination_speed.py 
Running extend timing test
1000 loops, 500 sets: 0.132 ms per loop, 0.263 us per set
Running queue timing test
1000 loops, 500 sets: 0.425 ms per loop, 0.851 us per set
Running set timing test
1000 loops, 500 sets: 0.313 ms per loop, 0.627 us per set

pypy3:

$ pypy3 test_recombination_speed.py 
Running extend timing test
1000 loops, 500 sets: 0.149 ms per loop, 0.297 us per set
Running queue timing test
1000 loops, 500 sets: 0.339 ms per loop, 0.677 us per set
Running set timing test
1000 loops, 500 sets: 0.236 ms per loop, 0.472 us per set

I'll merge as is and make a separate PR to switch back to my string-based version. Even if we later decide that the order of the indices isn't guaranteed to be sorted, we're sorting in the set version anyway, so it's not a big deal to sort a list instead of a set. Running the same tests where the extend version sorts first gives similar speeds between list and set.

There's some interesting stuff here. The pypy results are impressive.

Not sure I understand why this can be changed to elif here. Was the huge if statement being pointlessly broken up just so that info.weekday(l[i]) didn't need to be called twice?

If this is being switched for performance reasons, I guess we could check empirically to see which one runs the test suite faster.

Was the huge if statement being pointlessly broken up just so that info.weekday(l[i]) didn't need to be called twice?

AFAICT, yes. I was pretty sure that the big if blocks were mutually exclusive, but the number of continue statements, return (None, None), and exceptions made for enough code paths that I wanted to (n+1)-check. I chose to take the performance hit of a few extra dict lookups in order to make this obvious and have only one non-raising path through the loop.

I think that there's a question of adjudication if you find two things that have equal claim to being a time zone in the string. Right now I guess it just takes the most recent thing that it finds that matches?

Are these differences accumulating because you're reducing the number of passes through the loop?

These are because I am delaying incrementing i for as long as possible. This decreases the total number of places where i is incremented at all (41 down from 51). The closer i is to fixed within each iteration of the loop, the easier I find this to reason about.

This seems unused, and I'm somewhat dubious of its utility.

Agreed, removing it.

require is misspelled here.

Also, we absolutely cannot require len(token) >= 3, since Z is in the ISO8601 spec for Zulu time (UTC), unless we want to special-case this.

That said, when we fix this up, we may well be able to determine exactly the minimum and maximum length of all valid time zones. We can start by checking the length of all the keys of tzinfos.

Are these caught and re-raised in another form? Otherwise, they should be some ValueError subclass.

At the moment this still gets caught by the except (IndexError, ValueError, AssertionError) wrapping the big loop. When we eventually get rid of that catch-all, I agree that something like InvalidTimeError (which subclasses ValueError) would be more appropriate.