Efficient reverse line iterator

[6bc90104-76d0-45f1-9261-88125b361eb8]

BPO	1677872
Nosy	@rhettinger, @abalkin, @pitrou, @giampaolo, @tiran, @benjaminp, @merwok, @florentx, @james-emerton
Files	reverse_file_iterator.diff: Reverse file iterator implementation reverse-file-iterator-20071209.diff reverse-file-iterator-20071210.diff readprevline-20140415.diff: Implementation of BufferedReader.readprevline()

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = None closed_at = None created_at = labels = ['library', 'performance'] title = 'Efficient reverse line iterator' updated_at = user = 'https://bugs.python.org/marktrussell' ``` bugs.python.org fields: ```python activity = actor = 'jemerton' assignee = 'none' closed = False closed_date = None closer = None components = ['Library (Lib)'] creation = creator = 'mark_t_russell' dependencies = [] files = ['7854', '8902', '8913', '34894'] hgrepos = [] issue_num = 1677872 keywords = ['patch'] message_count = 12.0 messages = ['52152', '52153', '57266', '57269', '58326', '58361', '58370', '110532', '110533', '111041', '115651', '216381'] nosy_count = 11.0 nosy_names = ['rhettinger', 'belopolsky', 'pitrou', 'giampaolo.rodola', 'christian.heimes', 'mark_t_russell', 'benjamin.peterson', 'eric.araujo', 'flox', 'jcon', 'jemerton'] pr_nums = [] priority = 'normal' resolution = None stage = 'needs patch' status = 'open' superseder = None type = 'performance' url = 'https://bugs.python.org/issue1677872' versions = ['Python 3.3'] ```

Linked PRs

• gh-120710
• gh-120728

[6bc90104-76d0-45f1-9261-88125b361eb8]

This is an implementation of __reversed__ for the TextIOWrapper type from the new IO interface (see http://docs.google.com/Doc?id=dfksfvqd_1cn5g5m). It is used as:

    import io
    for line in reversed(io.open(filename)):
          ...

It is efficient (only reads a block at a time) but can handle arbitrary length lines. It is useful for scanning backwards through big log files, but my main reason for submitting it is as a demonstration of the usefulness of the new IO layers - it works by putting a new buffering layer round the RawIOBase object from the open() call.

It's just a proof of concept, but if there's interest in this I'm happy to write unit tests and documentation.

The patch also makes io.BufferedReader support buffering, and adds a very minimal implementation of io.TextIOBase and io.TextIOWrapper (needed to make io.open() work).

[rhettinger]

FWIW, I've wanted something like this for a long time (for scanning log files in reverse).

[tiran]

Some people like the feature, Guido isn't against the feature ... It looks as you have a good chance to get it into Python 3.0. :)

Can you come up with a new patch and unit tests? The io module has changed a lot since your initial patch.

[6bc90104-76d0-45f1-9261-88125b361eb8]

Sure - I'll do an updated patch at the weekend.

[6bc90104-76d0-45f1-9261-88125b361eb8]

Here's an updated version of the patch. Changes:

- Updated to work against current py3k branch (r59441)
- Added support for universal newlines
- Added unit tests
- Added docs

The patch includes documentation for reversed() and __reversed__() (in the library and reference manuals respectively) which are independent of the reverse lines iterator - I can split those out to separate patch if needed.

I also updated the expected output from test_profile and test_cProfile, although I think a better fix would be to filter out the stdlib-related stuff from the expected output, as currently these tests break whenever io.py is changed.

[gvanrossum]

I'd like to see the doc patches separated out and applied to 2.6 -- they'll automatically merge into 3.0 then. Make that a separate bug please.

I like the idea, haven't had time to carefully review the code, but noticed one oddity:

>> for line in reversed(open("/etc/passwd")): print(line, end="")

immediately raises

ValueError: I/O operation on closed file

[6bc90104-76d0-45f1-9261-88125b361eb8]

As Guido requested I've split off the generic reversed() and __reversed__() doc additions to this patch against 2.6: http://bugs.python.org/issue1582

The I/O error from reversed(open("/etc/passwd")) was caused by the inner TextIOWrapper calling close() (via the inherited IOBase.__del__() method). I've fixed it by having TextIOReverseIterator keep a reference to the file object, and added a test case for the bug.

I think it's at least questionable that TextIOWrapper.close() is calling buffer.close() on a buffer that it did not create. I assumed that keeping a reference to the buffer object would be enough to keep the buffer open, and I suspect this is likely to trip up others in future. I think TextIOWrapper.close() should probably just set a flag (for the use of its own closed() method) and rely on reference counting to call close() on the buffer object. If that sounds on the right lines I'm happy to think about it a bit more and submit a patch.

[83d2e70e-e599-4a04-b820-3814bbdb9bef]

The OP has done everything asked of him. There are a lot of positive comments about this request. Snag is the patch is in python, I understand that io is now written in C. Could we at this late stage get this into 3.2, or even a minor release of 3.2, or will it have to be deferred until 3.3?

[abalkin]

The OP has done everything asked of him.

Not quite. He split out the documentation part of his patch and it was accepted and committed.

Guido raised an issue with the code. OP raised more questions. The code was never updated.

Now the patch is out of date because io module has been reimplemented in C. The patch is still good as a prototype/proof of concept but needs to be updated to apply to _pyio.

The idea is good, but the implementation is not ready.

[6bc90104-76d0-45f1-9261-88125b361eb8]

I'll do a C version of the patch (hopefully in the next week or so).

[pitrou]

Suggestions:

• do it on BufferedReader, rather than TextIOWrapper: if you want full-speed scanning of log files, you probably want to open them in binary mode

• rather than implementing a full-blown iterator, you can start with simple primitives: e.g. a method called readprevline() (or even scan_back() if you want to make the stop character(s) configurable)

[28e43466-2b15-47ca-ad85-7d366f94c92c]

Attached is an implementation of BufferedReader.readprevline(), as suggested by Antoine.

At this point, it seems to be working but I would like to improve the tests when a single result spans multiple chunks. I would particularly like to ensure correct behaviour when a newline ends up as the last byte of a new chunk.

[gvanrossum]

Last activity was 2014. Anyone interested in getting this over the finish line?