text:
PEP: 471 Title: os.scandir() function -- a better and faster directory
iterator Version: $Revision$ Last-Modified: $Date$ Author: Ben Hoyt
<EMAIL_ADDRESS>BDFL-Delegate: Victor Stinner<EMAIL_ADDRESS>Status: Final Type: Standards Track Content-Type: text/x-rst Created:
30-May-2014 Python-Version: 3.5 Post-History: 27-Jun-2014, 08-Jul-2014,
14-Jul-2014

Abstract

This PEP proposes including a new directory iteration function,
os.scandir(), in the standard library. This new function adds useful
functionality and increases the speed of os.walk() by 2-20 times
(depending on the platform and file system) by avoiding calls to
os.stat() in most cases.

Rationale

Python's built-in os.walk() is significantly slower than it needs to be,
because -- in addition to calling os.listdir() on each directory -- it
executes the stat() system call or GetFileAttributes() on each file to
determine whether the entry is a directory or not.

But the underlying system calls -- FindFirstFile / FindNextFile on
Windows and readdir on POSIX systems --already tell you whether the
files returned are directories or not, so no further system calls are
needed. Further, the Windows system calls return all the information for
a stat_result object on the directory entry, such as file size and last
modification time.

In short, you can reduce the number of system calls required for a tree
function like os.walk() from approximately 2N to N, where N is the total
number of files and directories in the tree. (And because directory
trees are usually wider than they are deep, it's often much better than
this.)

In practice, removing all those extra system calls makes os.walk() about
8-9 times as fast on Windows, and about 2-3 times as fast on POSIX
systems. So we're not talking about micro-optimizations. See more
benchmarks here.

Somewhat relatedly, many people (see Python Issue 11406) are also keen
on a version of os.listdir() that yields filenames as it iterates
instead of returning them as one big list. This improves memory
efficiency for iterating very large directories.

So, as well as providing a scandir() iterator function for calling
directly, Python's existing os.walk() function can be sped up a huge
amount.

Implementation

The implementation of this proposal was written by Ben Hoyt (initial
version) and Tim Golden (who helped a lot with the C extension module).
It lives on GitHub at benhoyt/scandir. (The implementation may lag
behind the updates to this PEP a little.)

Note that this module has been used and tested (see "Use in the wild"
section in this PEP), so it's more than a proof-of-concept. However, it
is marked as beta software and is not extensively battle-tested. It will
need some cleanup and more thorough testing before going into the
standard library, as well as integration into posixmodule.c.

Specifics of proposal

os.scandir()

Specifically, this PEP proposes adding a single function to the os
module in the standard library, scandir, that takes a single, optional
string as its argument:

    scandir(path='.') -> generator of DirEntry objects

Like listdir, scandir calls the operating system's directory iteration
system calls to get the names of the files in the given path, but it's
different from listdir in two ways:

-   Instead of returning bare filename strings, it returns lightweight
    DirEntry objects that hold the filename string and provide simple
    methods that allow access to the additional data the operating
    system may have returned.
-   It returns a generator instead of a list, so that scandir acts as a
    true iterator instead of returning the full list immediately.

scandir() yields a DirEntry object for each file and sub-directory in
path. Just like listdir, the '.' and '..' pseudo-directories are
skipped, and the entries are yielded in system-dependent order. Each
DirEntry object has the following attributes and methods:

-   name: the entry's filename, relative to the scandir path argument
    (corresponds to the return values of os.listdir)
-   path: the entry's full path name (not necessarily an absolute path)
    -- the equivalent of os.path.join(scandir_path, entry.name)
-   inode(): return the inode number of the entry. The result is cached
    on the DirEntry object, use
    os.stat(entry.path, follow_symlinks=False).st_ino to fetch
    up-to-date information. On Unix, no system call is required.
-   is_dir(*, follow_symlinks=True): similar to pathlib.Path.is_dir(),
    but the return value is cached on the DirEntry object; doesn't
    require a system call in most cases; don't follow symbolic links if
    follow_symlinks is False
-   is_file(*, follow_symlinks=True): similar to pathlib.Path.is_file(),
    but the return value is cached on the DirEntry object; doesn't
    require a system call in most cases; don't follow symbolic links if
    follow_symlinks is False
-   is_symlink(): similar to pathlib.Path.is_symlink(), but the return
    value is cached on the DirEntry object; doesn't require a system
    call in most cases
-   stat(*, follow_symlinks=True): like os.stat(), but the return value
    is cached on the DirEntry object; does not require a system call on
    Windows (except for symlinks); don't follow symbolic links (like
    os.lstat()) if follow_symlinks is False

All methods may perform system calls in some cases and therefore
possibly raise OSError -- see the "Notes on exception handling" section
for more details.

The DirEntry attribute and method names were chosen to be the same as
those in the new pathlib module where possible, for consistency. The
only difference in functionality is that the DirEntry methods cache
their values on the entry object after the first call.

Like the other functions in the os module, scandir() accepts either a
bytes or str object for the path parameter, and returns the
DirEntry.name and DirEntry.path attributes with the same type as path.
However, it is strongly recommended to use the str type, as this ensures
cross-platform support for Unicode filenames. (On Windows, bytes
filenames have been deprecated since Python 3.3).

os.walk()

As part of this proposal, os.walk() will also be modified to use
scandir() rather than listdir() and os.path.isdir(). This will increase
the speed of os.walk() very significantly (as mentioned above, by 2-20
times, depending on the system).

Examples

First, a very simple example of scandir() showing use of the
DirEntry.name attribute and the DirEntry.is_dir() method:

    def subdirs(path):
        """Yield directory names not starting with '.' under given path."""
        for entry in os.scandir(path):
            if not entry.name.startswith('.') and entry.is_dir():
                yield entry.name

This subdirs() function will be significantly faster with scandir than
os.listdir() and os.path.isdir() on both Windows and POSIX systems,
especially on medium-sized or large directories.

Or, for getting the total size of files in a directory tree, showing use
of the DirEntry.stat() method and DirEntry.path attribute:

    def get_tree_size(path):
        """Return total size of files in given path and subdirs."""
        total = 0
        for entry in os.scandir(path):
            if entry.is_dir(follow_symlinks=False):
                total += get_tree_size(entry.path)
            else:
                total += entry.stat(follow_symlinks=False).st_size
        return total

This also shows the use of the follow_symlinks parameter to is_dir() --
in a recursive function like this, we probably don't want to follow
links. (To properly follow links in a recursive function like this we'd
want special handling for the case where following a symlink leads to a
recursive loop.)

Note that get_tree_size() will get a huge speed boost on Windows,
because no extra stat call are needed, but on POSIX systems the size
information is not returned by the directory iteration functions, so
this function won't gain anything there.

Notes on caching

The DirEntry objects are relatively dumb -- the name and path attributes
are obviously always cached, and the is_X and stat methods cache their
values (immediately on Windows via FindNextFile, and on first use on
POSIX systems via a stat system call) and never refetch from the system.

For this reason, DirEntry objects are intended to be used and thrown
away after iteration, not stored in long-lived data structured and the
methods called again and again.

If developers want "refresh" behaviour (for example, for watching a
file's size change), they can simply use pathlib.Path objects, or call
the regular os.stat() or os.path.getsize() functions which get fresh
data from the operating system every call.

Notes on exception handling

DirEntry.is_X() and DirEntry.stat() are explicitly methods rather than
attributes or properties, to make it clear that they may not be cheap
operations (although they often are), and they may do a system call. As
a result, these methods may raise OSError.

For example, DirEntry.stat() will always make a system call on
POSIX-based systems, and the DirEntry.is_X() methods will make a stat()
system call on such systems if readdir() does not support d_type or
returns a d_type with a value of DT_UNKNOWN, which can occur under
certain conditions or on certain file systems.

Often this does not matter -- for example, os.walk() as defined in the
standard library only catches errors around the listdir() calls.

Also, because the exception-raising behaviour of the DirEntry.is_X
methods matches that of pathlib -- which only raises OSError in the case
of permissions or other fatal errors, but returns False if the path
doesn't exist or is a broken symlink -- it's often not necessary to
catch errors around the is_X() calls.

However, when a user requires fine-grained error handling, it may be
desirable to catch OSError around all method calls and handle as
appropriate.

For example, below is a version of the get_tree_size() example shown
above, but with fine-grained error handling added:

    def get_tree_size(path):
        """Return total size of files in path and subdirs. If
        is_dir() or stat() fails, print an error message to stderr
        and assume zero size (for example, file has been deleted).
        """
        total = 0
        for entry in os.scandir(path):
            try:
                is_dir = entry.is_dir(follow_symlinks=False)
            except OSError as error:
                print('Error calling is_dir():', error, file=sys.stderr)
                continue
            if is_dir:
                total += get_tree_size(entry.path)
            else:
                try:
                    total += entry.stat(follow_symlinks=False).st_size
                except OSError as error:
                    print('Error calling stat():', error, file=sys.stderr)
        return total

Support

The scandir module on GitHub has been forked and used quite a bit (see
"Use in the wild" in this PEP), but there's also been a fair bit of
direct support for a scandir-like function from core developers and
others on the python-dev and python-ideas mailing lists. A sampling:

-   python-dev: a good number of +1's and very few negatives for scandir
    and PEP 471 on this June 2014 python-dev thread
-   Alyssa Coghlan, a core Python developer: "I've had the local Red Hat
    release engineering team express their displeasure at having to stat
    every file in a network mounted directory tree for info that is
    present in the dirent structure, so a definite +1 to os.scandir from
    me, so long as it makes that info available." [source1]
-   Tim Golden, a core Python developer, supports scandir enough to have
    spent time refactoring and significantly improving scandir's C
    extension module. [source2]
-   Christian Heimes, a core Python developer: "+1 for something like
    yielddir()" [source3] and "Indeed! I'd like to see the feature in
    3.4 so I can remove my own hack from our code base." [source4]
-   Gregory P. Smith, a core Python developer: "As 3.4beta1 happens
    tonight, this isn't going to make 3.4 so i'm bumping this to 3.5. I
    really like the proposed design outlined above." [source5]
-   Guido van Rossum on the possibility of adding scandir to Python 3.5
    (as it was too late for 3.4): "The ship has likewise sailed for
    adding scandir() (whether to os or pathlib). By all means experiment
    and get it ready for consideration for 3.5, but I don't want to add
    it to 3.4." [source6]

Support for this PEP itself (meta-support?) was given by Alyssa (Nick)
Coghlan on python-dev: "A PEP reviewing all this for 3.5 and proposing a
specific os.scandir API would be a good thing." [source7]

Use in the wild

To date, the scandir implementation is definitely useful, but has been
clearly marked "beta", so it's uncertain how much use of it there is in
the wild. Ben Hoyt has had several reports from people using it. For
example:

-   Chris F: "I am processing some pretty large directories and was half
    expecting to have to modify getdents. So thanks for saving me the
    effort." [via personal email]
-   bschollnick: "I wanted to let you know about this, since I am using
    Scandir as a building block for this code. Here's a good example of
    scandir making a radical performance improvement over os.listdir."
    [source8]
-   Avram L: "I'm testing our scandir for a project I'm working on.
    Seems pretty solid, so first thing, just want to say nice work!"
    [via personal email]
-   Matt Z: "I used scandir to dump the contents of a network dir in
    under 15 seconds. 13 root dirs, 60,000 files in the structure. This
    will replace some old VBA code embedded in a spreadsheet that was
    taking 15-20 minutes to do the exact same thing." [via personal
    email]

Others have requested a PyPI package for it, which has been created. See
PyPI package.

GitHub stats don't mean too much, but scandir does have several
watchers, issues, forks, etc. Here's the run-down as of the stats as of
July 7, 2014:

-   Watchers: 17
-   Stars: 57
-   Forks: 20
-   Issues: 4 open, 26 closed

Also, because this PEP will increase the speed of os.walk()
significantly, there are thousands of developers and scripts, and a lot
of production code, that would benefit from it. For example, on GitHub,
there are almost as many uses of os.walk (194,000) as there are of
os.mkdir (230,000).

Rejected ideas

Naming

The only other real contender for this function's name was iterdir().
However, iterX() functions in Python (mostly found in Python 2) tend to
be simple iterator equivalents of their non-iterator counterparts. For
example, dict.iterkeys() is just an iterator version of dict.keys(), but
the objects returned are identical. In scandir()'s case, however, the
return values are quite different objects (DirEntry objects vs filename
strings), so this should probably be reflected by a difference in name
-- hence scandir().

See some relevant discussion on python-dev.

Wildcard support

FindFirstFile/FindNextFile on Windows support passing a "wildcard" like
*.jpg, so at first folks (this PEP's author included) felt it would be a
good idea to include a windows_wildcard keyword argument to the scandir
function so users could pass this in.

However, on further thought and discussion it was decided that this
would be bad idea, unless it could be made cross-platform (a pattern
keyword argument or similar). This seems easy enough at first -- just
use the OS wildcard support on Windows, and something like fnmatch or re
afterwards on POSIX-based systems.

Unfortunately the exact Windows wildcard matching rules aren't really
documented anywhere by Microsoft, and they're quite quirky (see this
blog post), meaning it's very problematic to emulate using fnmatch or
regexes.

So the consensus was that Windows wildcard support was a bad idea. It
would be possible to add at a later date if there's a cross-platform way
to achieve it, but not for the initial version.

Read more on the this Nov 2012 python-ideas thread and this June 2014
python-dev thread on PEP 471.

Methods not following symlinks by default

There was much debate on python-dev (see messages in this thread) over
whether the DirEntry methods should follow symbolic links or not (when
the is_X() methods had no follow_symlinks parameter).

Initially they did not (see previous versions of this PEP and the
scandir.py module), but Victor Stinner made a pretty compelling case on
python-dev that following symlinks by default is a better idea, because:

-   following links is usually what you want (in 92% of cases in the
    standard library, functions using os.listdir() and os.path.isdir()
    do follow symlinks)
-   that's the precedent set by the similar functions os.path.isdir()
    and pathlib.Path.is_dir(), so to do otherwise would be confusing
-   with the non-link-following approach, if you wanted to follow links
    you'd have to say something like
    if (entry.is_symlink() and os.path.isdir(entry.path)) or entry.is_dir(),
    which is clumsy

As a case in point that shows the non-symlink-following version is error
prone, this PEP's author had a bug caused by getting this exact test
wrong in his initial implementation of scandir.walk() in scandir.py (see
Issue #4 here).

In the end there was not total agreement that the methods should follow
symlinks, but there was basic consensus among the most involved
participants, and this PEP's author believes that the above case is
strong enough to warrant following symlinks by default.

In addition, it's straightforward to call the relevant methods with
follow_symlinks=False if the other behaviour is desired.

DirEntry attributes being properties

In some ways it would be nicer for the DirEntry is_X() and stat() to be
properties instead of methods, to indicate they're very cheap or free.
However, this isn't quite the case, as stat() will require an OS call on
POSIX-based systems but not on Windows. Even is_dir() and friends may
perform an OS call on POSIX-based systems if the dirent.d_type value is
DT_UNKNOWN (on certain file systems).

Also, people would expect the attribute access entry.is_dir to only ever
raise AttributeError, not OSError in the case it makes a system call
under the covers. Calling code would have to have a try/except around
what looks like a simple attribute access, and so it's much better to
make them methods.

See this May 2013 python-dev thread where this PEP author makes this
case and there's agreement from a core developers.

DirEntry fields being "static" attribute-only objects

In this July 2014 python-dev message, Paul Moore suggested a solution
that was a "thin wrapper round the OS feature", where the DirEntry
object had only static attributes: name, path, and is_X, with the st_X
attributes only present on Windows. The idea was to use this simpler,
lower-level function as a building block for higher-level functions.

At first there was general agreement that simplifying in this way was a
good thing. However, there were two problems with this approach. First,
the assumption is the is_dir and similar attributes are always present
on POSIX, which isn't the case (if d_type is not present or is
DT_UNKNOWN). Second, it's a much harder-to-use API in practice, as even
the is_dir attributes aren't always present on POSIX, and would need to
be tested with hasattr() and then os.stat() called if they weren't
present.

See this July 2014 python-dev response from this PEP's author detailing
why this option is a non-ideal solution, and the subsequent reply from
Paul Moore voicing agreement.

DirEntry fields being static with an ensure_lstat option

Another seemingly simpler and attractive option was suggested by Alyssa
Coghlan in this June 2014 python-dev message: make DirEntry.is_X and
DirEntry.lstat_result properties, and populate DirEntry.lstat_result at
iteration time, but only if the new argument ensure_lstat=True was
specified on the scandir() call.

This does have the advantage over the above in that you can easily get
the stat result from scandir() if you need it. However, it has the
serious disadvantage that fine-grained error handling is messy, because
stat() will be called (and hence potentially raise OSError) during
iteration, leading to a rather ugly, hand-made iteration loop:

    it = os.scandir(path)
    while True:
        try:
            entry = next(it)
        except OSError as error:
            handle_error(path, error)
        except StopIteration:
            break

Or it means that scandir() would have to accept an onerror argument -- a
function to call when stat() errors occur during iteration. This seems
to this PEP's author neither as direct nor as Pythonic as try/except
around a DirEntry.stat() call.

Another drawback is that os.scandir() is written to make code faster.
Always calling os.lstat() on POSIX would not bring any speedup. In most
cases, you don't need the full stat_result object -- the is_X() methods
are enough and this information is already known.

See Ben Hoyt's July 2014 reply to the discussion summarizing this and
detailing why he thinks the original PEP 471 proposal is "the right one"
after all.

Return values being (name, stat_result) two-tuples

Initially this PEP's author proposed this concept as a function called
iterdir_stat() which yielded two-tuples of (name, stat_result). This
does have the advantage that there are no new types introduced. However,
the stat_result is only partially filled on POSIX-based systems (most
fields set to None and other quirks), so they're not really stat_result
objects at all, and this would have to be thoroughly documented as
different from os.stat().

Also, Python has good support for proper objects with attributes and
methods, which makes for a saner and simpler API than two-tuples. It
also makes the DirEntry objects more extensible and future-proof as
operating systems add functionality and we want to include this in
DirEntry.

See also some previous discussion:

-   May 2013 python-dev thread where Alyssa Coghlan makes the original
    case for a DirEntry-style object.
-   June 2014 python-dev thread where Alyssa Coghlan makes (another)
    good case against the two-tuple approach.

Return values being overloaded stat_result objects

Another alternative discussed was making the return values to be
overloaded stat_result objects with name and path attributes. However,
apart from this being a strange (and strained!) kind of overloading,
this has the same problems mentioned above --most of the stat_result
information is not fetched by readdir() on POSIX systems, only (part of)
the st_mode value.

Return values being pathlib.Path objects

With Antoine Pitrou's new standard library pathlib module, it at first
seems like a great idea for scandir() to return instances of
pathlib.Path. However, pathlib.Path's is_X() and stat() functions are
explicitly not cached, whereas scandir has to cache them by design,
because it's (often) returning values from the original directory
iteration system call.

And if the pathlib.Path instances returned by scandir cached stat
values, but the ordinary pathlib.Path objects explicitly don't, that
would be more than a little confusing.

Guido van Rossum explicitly rejected pathlib.Path caching stat in the
context of scandir here, making pathlib.Path objects a bad choice for
scandir return values.

Possible improvements

There are many possible improvements one could make to scandir, but here
is a short list of some this PEP's author has in mind:

-   scandir could potentially be further sped up by calling readdir /
    FindNextFile say 50 times per Py_BEGIN_ALLOW_THREADS block so that
    it stays in the C extension module for longer, and may be somewhat
    faster as a result. This approach hasn't been tested, but was
    suggested by on Issue 11406 by Antoine Pitrou. [source9]
-   scandir could use a free list to avoid the cost of memory allocation
    for each iteration -- a short free list of 10 or maybe even 1 may
    help. Suggested by Victor Stinner on a python-dev thread on June 27.

Previous discussion

-   Original November 2012 thread Ben Hoyt started on python-ideas about
    speeding up os.walk()
-   Python Issue 11406, which includes the original proposal for a
    scandir-like function
-   Further May 2013 thread Ben Hoyt started on python-dev that refined
    the scandir() API, including Alyssa Coghlan's suggestion of scandir
    yielding DirEntry-like objects
-   November 2013 thread Ben Hoyt started on python-dev to discuss the
    interaction between scandir and the new pathlib module
-   June 2014 thread Ben Hoyt started on python-dev to discuss the first
    version of this PEP, with extensive discussion about the API
-   First July 2014 thread Ben Hoyt started on python-dev to discuss his
    updates to PEP 471
-   Second July 2014 thread Ben Hoyt started on python-dev to discuss
    the remaining decisions needed to finalize PEP 471, specifically
    whether the DirEntry methods should follow symlinks by default
-   Question on StackOverflow about why os.walk() is slow and pointers
    on how to fix it (this inspired the author of this PEP early on)
-   BetterWalk, this PEP's author's previous attempt at this, on which
    the scandir code is based

Copyright

This document has been placed in the public domain.

  Local Variables: mode: indented-text indent-tabs-mode: nil
  sentence-end-double-space: t fill-column: 70 coding: utf-8 End:


text:
PEP: 3114 Title: Renaming iterator.next() to iterator.__next__() Author:
Ka-Ping Yee<EMAIL_ADDRESS>Status: Final Type: Standards Track
Content-Type: text/x-rst Created: 04-Mar-2007 Python-Version: 3.0
Post-History:

Abstract

The iterator protocol in Python 2.x consists of two methods: __iter__()
called on an iterable object to yield an iterator, and next() called on
an iterator object to yield the next item in the sequence. Using a for
loop to iterate over an iterable object implicitly calls both of these
methods. This PEP proposes that the next method be renamed to __next__,
consistent with all the other protocols in Python in which a method is
implicitly called as part of a language-level protocol, and that a
built-in function named next be introduced to invoke __next__ method,
consistent with the manner in which other protocols are explicitly
invoked.

Names With Double Underscores

In Python, double underscores before and after a name are used to
distinguish names that belong to the language itself. Attributes and
methods that are implicitly used or created by the interpreter employ
this naming convention; some examples are:

-   __file__ - an attribute automatically created by the interpreter
-   __dict__ - an attribute with special meaning to the interpreter
-   __init__ - a method implicitly called by the interpreter

Note that this convention applies to methods such as __init__ that are
explicitly defined by the programmer, as well as attributes such as
__file__ that can only be accessed by naming them explicitly, so it
includes names that are used or created by the interpreter.

(Not all things that are called "protocols" are made of methods with
double-underscore names. For example, the __contains__ method has double
underscores because the language construct x in y implicitly calls
__contains__. But even though the read method is part of the file
protocol, it does not have double underscores because there is no
language construct that implicitly invokes x.read().)

The use of double underscores creates a separate namespace for names
that are part of the Python language definition, so that programmers are
free to create variables, attributes, and methods that start with
letters, without fear of silently colliding with names that have a
language-defined purpose. (Colliding with reserved keywords is still a
concern, but at least this will immediately yield a syntax error.)

The naming of the next method on iterators is an exception to this
convention. Code that nowhere contains an explicit call to a next method
can nonetheless be silently affected by the presence of such a method.
Therefore, this PEP proposes that iterators should have a __next__
method instead of a next method (with no change in semantics).

Double-Underscore Methods and Built-In Functions

The Python language defines several protocols that are implemented or
customized by defining methods with double-underscore names. In each
case, the protocol is provided by an internal method implemented as a C
function in the interpreter. For objects defined in Python, this C
function supports customization by implicitly invoking a Python method
with a double-underscore name (it often does a little bit of additional
work beyond just calling the Python method.)

Sometimes the protocol is invoked by a syntactic construct:

-   x[y] --> internal tp_getitem --> x.__getitem__(y)
-   x + y --> internal nb_add --> x.__add__(y)
-   -x --> internal nb_negative --> x.__neg__()

Sometimes there is no syntactic construct, but it is still useful to be
able to explicitly invoke the protocol. For such cases Python offers a
built-in function of the same name but without the double underscores.

-   len(x) --> internal sq_length --> x.__len__()
-   hash(x) --> internal tp_hash --> x.__hash__()
-   iter(x) --> internal tp_iter --> x.__iter__()

Following this pattern, the natural way to handle next is to add a next
built-in function that behaves in exactly the same fashion.

-   next(x) --> internal tp_iternext --> x.__next__()

Further, it is proposed that the next built-in function accept a
sentinel value as an optional second argument, following the style of
the getattr and iter built-in functions. When called with two arguments,
next catches the StopIteration exception and returns the sentinel value
instead of propagating the exception. This creates a nice duality
between iter and next:

  iter(function, sentinel) <--> next(iterator, sentinel)

Previous Proposals

This proposal is not a new idea. The idea proposed here was supported by
the BDFL on python-dev[1] and is even mentioned in the original iterator
PEP, PEP 234:

    (In retrospect, it might have been better to go for __next__()
    and have a new built-in, next(it), which calls it.__next__().
    But alas, it's too late; this has been deployed in Python 2.2
    since December 2001.)

Objections

There have been a few objections to the addition of more built-ins. In
particular, Martin von Loewis writes[2]:

    I dislike the introduction of more builtins unless they have a true
    generality (i.e. are likely to be needed in many programs). For this
    one, I think the normal usage of __next__ will be with a for loop, so
    I don't think one would often need an explicit next() invocation.

    It is also not true that most protocols are explicitly invoked through
    builtin functions. Instead, most protocols are can be explicitly invoked
    through methods in the operator module. So following tradition, it
    should be operator.next.

    ...

    As an alternative, I propose that object grows a .next() method,
    which calls __next__ by default.

Transition Plan

Two additional transformations will be added to the 2to3 translation
tool[3]:

-   Method definitions named next will be renamed to __next__.
-   Explicit calls to the next method will be replaced with calls to the
    built-in next function. For example, x.next() will become next(x).

Collin Winter looked into the possibility of automatically deciding
whether to perform the second transformation depending on the presence
of a module-level binding to next[4] and found that it would be "ugly
and slow". Instead, the translation tool will emit warnings upon
detecting such a binding. Collin has proposed warnings for the following
conditions[5]:

-   Module-level assignments to next.
-   Module-level definitions of a function named next.
-   Module-level imports of the name next.
-   Assignments to __builtin__.next.

Approval

This PEP was accepted by Guido on March 6, 2007[6].

Implementation

A patch with the necessary changes (except the 2to3 tool) was written by
Georg Brandl and committed as revision 54910.

References

Copyright

This document has been placed in the public domain.

[1] Single- vs. Multi-pass iterability (Guido van Rossum)
https://mail.python.org/pipermail/python-dev/2002-July/026814.html

[2] PEP: rename it.next() to it.__next__()... (Martin von Loewis)
https://mail.python.org/pipermail/python-3000/2007-March/005965.html

[3] 2to3 refactoring tool
https://github.com/python/cpython/tree/ef04c44e29a8276a484f58d03a75a2dec516302d/Lib/lib2to3

[4] PEP: rename it.next() to it.__next__()... (Collin Winter)
https://mail.python.org/pipermail/python-3000/2007-March/006020.html

[5] PEP 3113 transition plan
https://mail.python.org/pipermail/python-3000/2007-March/006044.html

[6] PEP: rename it.next() to it.__next__()... (Guido van Rossum)
https://mail.python.org/pipermail/python-3000/2007-March/006027.html

license: Public Domain


text:
PEP: 740 Title: Index support for digital attestations Author: William
Woodruff<EMAIL_ADDRESS>Facundo Tuesca
<EMAIL_ADDRESS>Dustin Ingram<EMAIL_ADDRESS>Sponsor:
Donald Stufft<EMAIL_ADDRESS>PEP-Delegate: Donald Stufft
<EMAIL_ADDRESS>Discussions-To:
https://discuss.python.org/t/pep-740-index-support-for-digital-attestations/44498
Status: Provisional Type: Standards Track Topic: Packaging Created:
08-Jan-2024 Post-History: 02-Jan-2024, 29-Jan-2024 Resolution:
https://discuss.python.org/t/pep-740-index-support-for-digital-attestations/44498/26

Abstract

This PEP proposes a collection of changes related to the upload and
distribution of digitally signed attestations and metadata used to
verify them on a Python package repository, such as PyPI.

These changes have two subcomponents:

-   Changes to the currently unstandardized PyPI upload API, allowing
    clients to upload digital attestations as
    attestation objects <attestation-object>;
-   Changes to the
    HTML and JSON "simple" APIs <packaging:simple-repository-api>,
    allowing clients to retrieve both digital attestations and Trusted
    Publishing metadata for individual release files as
    provenance objects <provenance-object>.

This PEP does not make a policy recommendation around mandatory digital
attestations on release uploads or their subsequent verification by
installing clients like pip.

Rationale and Motivation

Desire for digital signatures on Python packages has been repeatedly
expressed by both package maintainers and downstream users:

-   Maintainers wish to demonstrate the integrity and authenticity of
    their package uploads;
-   Individual downstream users wish to verify package integrity and
    authenticity without placing additional trust in their index's
    honesty;
-   "Bulk" downstream users (such as Operating System distributions)
    wish to perform similar verifications and potentially re-expose or
    countersign for their own downstream packaging ecosystems.

This proposal seeks to accommodate each of the above use cases.

Additionally, this proposal identifies the following motivations:

-   Verifiable provenance for Python package distributions: many Python
    packages currently contain unauthenticated provenance metadata, such
    as URLs for source hosts. A cryptographic attestation format could
    enable strong authenticated links between these packages and their
    source hosts, allowing both the index and downstream users to
    cryptographically verify that a package originates from its claimed
    source repository.

-   Raising attacker requirements: an attacker who seeks to take over a
    Python package can be described along sophistication
    (unsophisticated to sophisticated) and targeting dimensions
    (opportunistic to targeted).

    Digital attestations impose additional sophistication requirements:
    the attacker must be sufficiently sophisticated to access private
    signing material (or signing identities).

-   Index verifiability: in the status quo, the only attestation
    provided by the index is an optional PGP signature per release file
    (see PGP signatures <pgp-signatures>). These signatures are not (and
    cannot be) checked by the index either for well-formedness or for
    validity, since the index has no mechanism for identifying the right
    public key for the signature. This PEP overcomes this limitation by
    ensuring that provenance objects <provenance-object> contain all of
    the metadata needed by the index to verify an attestation's
    validity.

This PEP proposes a generic attestation format, containing an
attestation statement for signature generation <payload-and-signature-generation>,
with the expectation that index providers adopt the format with a
suitable source of identity for signature verification, such as Trusted
Publishing.

Design Considerations

This PEP identifies the following design considerations when evaluating
both its own proposed changes and previous work in the same or adjacent
areas of Python packaging:

1.  Index accessibility: digital attestations for Python packages are
    ideally retrievable directly from the index itself, as "detached"
    resources.

    This both simplifies some compatibility concerns (by avoiding the
    need to modify the distribution formats themselves) and also
    simplifies the behavior of potential installing clients (by allowing
    them to retrieve each attestation before its corresponding package
    without needing to do streaming decompression).

2.  Verification by the index itself: in addition to enabling
    verification by installing clients, each digital attestation is
    ideally verifiable in some form by the index itself.

    This both increases the overall quality of attestations uploaded to
    the index (preventing, for example, users from accidentally
    uploading incorrect or invalid attestations) and also enables UI and
    UX refinements on the index itself (such as a "provenance" view for
    each uploaded package).

3.  General applicability: digital attestations should be applicable to
    any and every package uploaded to the index, regardless of its
    format (sdist or wheel) or interior contents.

4.  Metadata support: this PEP refers to "digital attestations" rather
    than just "digital signatures" to emphasize the ideal presence of
    additional metadata within the cryptographic envelope.

    For example, to prevent domain separation between a distribution's
    name and its contents, this PEP uses 'Statements' from the in-toto
    project to bind the distribution's contents (via SHA-256 digest) to
    its filename.

Previous Work

PGP signatures

PyPI and other indices have historically supported PGP signatures on
uploaded distributions. These could be supplied during upload, and could
be retrieved by installing clients via the data-gpg-sig attribute in the
PEP 503 API, the gpg-sig key on the PEP 691 API, or via an adjacent
.asc-suffixed URL.

PGP signature uploads have been disabled on PyPI since May 2023, after
an investigation determined that the majority of signatures (which,
themselves, constituted a tiny percentage of overall uploads) could not
be associated with a public key or otherwise meaningfully verified.

In their previously supported form on PyPI, PGP signatures satisfied
considerations (1) and (3) above but not (2) (owing to the need for
external keyservers and key distribution) or (4) (due to PGP signatures
typically being constructed over just an input file, without any
associated signed metadata).

Wheel signatures

PEP 427 (and its
living PyPA counterpart <packaging:binary-distribution-format>) specify
the wheel format <packaging:Wheel>.

This format includes accommodations for digital signatures embedded
directly into the wheel, in either JWS or S/MIME format. These
signatures are specified over a PEP 376 RECORD, which is modified to
include a cryptographic digest for each recorded file in the wheel.

While wheel signatures are fully specified, they do not appear to be
broadly used; the official wheel tooling deprecated signature generation
and verification support in 0.32.0, which was released in 2018.

Additionally, wheel signatures do not satisfy any of the above
considerations (due to the "attached" nature of the signatures,
non-verifiability on the index itself, and support for wheels only).

Specification

Upload endpoint changes

The current upload API is not standardized. However, we propose the
following changes to it:

-   In addition to the current top-level content and gpg_signature
    fields, the index SHALL accept attestations as an additional
    multipart form field.
-   The new attestations field SHALL be a JSON array.
-   The attestations array SHALL have one or more items, each a JSON
    object representing an individual attestation.
-   Each attestation object MUST be verifiable by the index. If the
    index fails to verify any attestation in attestations, it MUST
    reject the upload. The format of attestation objects is defined
    under attestation-object and the process for verifying attestations
    is defined under attestation-verification.

Index changes

Simple Index

The following changes are made to the
simple repository API <packaging:simple-repository-api-base>:

-   When an uploaded file has one or more attestations, the index MAY
    provide a provenance file containing attestations associated with a
    given distribution. The format of the provenance file SHALL be a
    JSON-encoded provenance object <provenance-object>, which SHALL
    contain the file's attestations.

    The location of the provenance file is signaled by the index via the
    data-provenance attribute.

-   When a provenance file is present, the index MAY include a
    data-provenance attribute on its file link. The value of the
    data-provenance attribute SHALL be a fully qualified URL, signaling
    the the file's provenance can be found at that URL. This URL MUST
    represent a secure origin.

    The following table provides examples of release file URLs,
    data-provenance values, and their resulting provenance file URLs.

      File URL                                         data-provenance                                                   Provenance URL
      ------------------------------------------------ ----------------------------------------------------------------- -----------------------------------------------------------------
      https://example.com/sampleproject-1.2.3.tar.gz   https://example.com/sampleproject-1.2.3.tar.gz.provenance         https://example.com/sampleproject-1.2.3.tar.gz.provenance
      https://example.com/sampleproject-1.2.3.tar.gz   https://other.example.com/sampleproject-1.2.3.tar.gz/provenance   https://other.example.com/sampleproject-1.2.3.tar.gz/provenance
      https://example.com/sampleproject-1.2.3.tar.gz   ../relative                                                       (invalid: not a fully qualified URL)
      https://example.com/sampleproject-1.2.3.tar.gz   http://unencrypted.example.com/provenance                         (invalid: not a secure origin)

-   The index MAY choose to modify the provenance file. For example, the
    index MAY permit adding additional attestations and verification
    materials, such as attestations from third-party auditors or other
    services.

    See changes-to-provenance-objects for an additional discussion of
    reasons why a file's provenance may change.

JSON-based Simple API

The following changes are made to the
JSON simple API <packaging:simple-repository-api-json>:

-   When an uploaded file has one or more attestations, the index MAY
    include a provenance key in the file dictionary for that file.

    The value of the provenance key SHALL be either a JSON string or
    null. If provenance is not null, it SHALL be a URL to the associated
    provenance file.

    See appendix-3 for an explanation of the technical decision to embed
    the SHA-256 digest in the JSON API, rather than the full
    provenance object <provenance-object>.

These changes require a version change to the JSON API:

-   The api-version SHALL specify version 1.3 or later.

Attestation objects

An attestation object is a JSON object with several required keys;
applications or signers may include additional keys so long as all
explicitly listed keys are provided. The required layout of an
attestation object is provided as pseudocode below.

    @dataclass
    class Attestation:
        version: Literal[1]
        """
        The attestation object's version, which is always 1.
        """

        verification_material: VerificationMaterial
        """
        Cryptographic materials used to verify `envelope`.
        """

        envelope: Envelope
        """
        The enveloped attestation statement and signature.
        """

    @dataclass
    class Envelope:
        statement: bytes
        """
        The attestation statement.

        This is represented as opaque bytes on the wire (encoded as base64),
        but it MUST be an JSON in-toto v1 Statement.
        """

        signature: bytes
        """
        A signature for the above statement, encoded as base64.
        """

    @dataclass
    class VerificationMaterial:
        certificate: str
        """
        The signing certificate, as `base64(DER(cert))`.
        """

        transparency_entries: list[object]
        """
        One or more transparency log entries for this attestation's signature
        and certificate.
        """

A full data model for each object in transparency_entries is provided in
appendix-2. Attestation objects SHOULD include one or more transparency
log entries, and MAY include additional keys for other sources of signed
time (such as an 3161 Time Stamping Authority or a Roughtime server).

Attestation objects are versioned; this PEP specifies version 1. Each
version is tied to a single cryptographic suite to minimize unnecessary
cryptographic agility. In version 1, the suite is as follows:

-   Certificates are specified as X.509 certificates, and comply with
    the profile in 5280.
-   The message signature algorithm is ECDSA, with the P-256 curve for
    public keys and SHA-256 as the cryptographic digest function.

Future PEPs may change this suite (and the overall shape of the
attestation object) by selecting a new version number.

Attestation statement and signature generation

The attestation statement is the actual claim that is cryptographically
signed over within the attestation object (i.e., the
envelope.statement).

The attestation statement is encoded as a v1 in-toto Statement object,
in JSON form. When serialized the statement is treated as an opaque
binary blob, avoiding the need for canonicalization. An example
JSON-encoded statement is provided in appendix-4.

In addition to being a v1 in-toto Statement, the attestation statement
is constrained in the following ways:

-   The in-toto subject MUST contain only a single subject.
-   subject[0].name is the distribution's filename, which MUST be a
    valid source distribution <packaging:source-distribution-format> or
    wheel distribution <packaging:binary-distribution-format> filename.
-   subject[0].digest MUST contain a SHA-256 digest. Other digests MAY
    be present. The digests MUST be represented as hexadecimal strings.
-   The following predicateType values are supported:
    -   SLSA Provenance: https://slsa.dev/provenance/v1
    -   PyPI Publish Attestation:
        https://docs.pypi.org/attestations/publish/v1

The signature over this statement is constructed using the v1 DSSE
signature protocol, with a PAYLOAD_TYPE of application/vnd.in-toto+json
and a PAYLOAD_BODY of the JSON-encoded statement above. No other
PAYLOAD_TYPE is permitted.

Provenance objects

The index will serve uploaded attestations along with metadata that can
assist in verifying them in the form of JSON serialized objects.

These provenance objects will be available via both the Simple Index and
JSON-based Simple API as described above, and will have the following
layout:

    {
        "version": 1,
        "attestation_bundles": [
          {
            "publisher": {
              "kind": "important-ci-service",
              "claims": {},
              "vendor-property": "foo",
              "another-property": 123
            },
            "attestations": [
              { /* attestation 1 ... */ },
              { /* attestation 2 ... */ }
            ]
          }
        ]
    }

or, as pseudocode:

    @dataclass
    class Publisher:
        kind: string
        """
        The kind of Trusted Publisher.
        """

        claims: object | None
        """
        Any context-specific claims retained by the index during Trusted Publisher
        authentication.
        """

        _rest: object
        """
        Each publisher object is open-ended, meaning that it MAY contain additional
        fields beyond the ones specified explicitly above. This field signals that,
        but is not itself present.
        """

    @dataclass
    class AttestationBundle:
        publisher: Publisher
        """
        The publisher associated with this set of attestations.
        """

        attestations: list[Attestation]
        """
        The set of attestations included in this bundle.
        """

    @dataclass
    class Provenance:
        version: Literal[1]
        """
        The provenance object's version, which is always 1.
        """

        attestation_bundles: list[AttestationBundle]
        """
        One or more attestation "bundles".
        """

-   version is 1. Like attestation objects, provenance objects are
    versioned, and this PEP only defines version 1.

-   attestation_bundles is a required JSON array, containing one or more
    "bundles" of attestations. Each bundle corresponds to a signing
    identity (such as a Trusted Publishing identity), and contains one
    or more attestation objects.

    As noted in the Publisher model, each AttestationBundle.publisher
    object is specific to its Trusted Publisher but must include at
    minimum:

    -   A kind key, which MUST be a JSON string that uniquely identifies
        the kind of Trusted Publisher.
    -   A claims key, which MUST be a JSON object containing any
        context-specific claims retained by the index during Trusted
        Publisher authentication.

    All other keys in the publisher object are publisher-specific. A
    full illustrative example of a publisher object is provided in
    appendix-1.

    Each array of attestation objects is a superset of the attestations
    array supplied by the uploaded through the attestations field at
    upload time, as described in upload-endpoint and
    changes-to-provenance-objects.

Changes to provenance objects

Provenance objects are not immutable, and may change over time. Reasons
for changes to the provenance object include but are not limited to:

-   Addition of new attestations for a pre-existing signing identity:
    the index MAY choose to allow additional attestations by
    pre-existing signing identities, such as newer attestation versions
    for already uploaded files.
-   Addition of new signing identities and associated attestations: the
    index MAY choose to support attestations from sources other than the
    file's uploader, such as third-party auditors or the index itself.
    These attestations may be performed asynchronously, requiring the
    index to insert them into the provenance object post facto.

Attestation verification

Verifying an attestation object against a distribution file requires
verification of each of the following:

-   version is 1. The verifier MUST reject any other version.
-   verification_material.certificate is a valid signing certificate, as
    issued by an a priori trusted authority (such as a root of trust
    already present within the verifying client).
-   verification_material.certificate identifies an appropriate signing
    subject, such as the machine identity of the Trusted Publisher that
    published the package.
-   envelope.statement is a valid in-toto v1 Statement, with a subject
    and digest that MUST match the distribution's filename and contents.
    For the distribution's filename, matching MUST be performed by
    parsing using the appropriate source distribution or wheel filename
    format, as the statement's subject may be equivalent but normalized.
-   envelope.signature is a valid signature for envelope.statement
    corresponding to verification_material.certificate, as reconstituted
    via the v1 DSSE signature protocol.

In addition to the above required steps, a verifier MAY additionally
verify verification_material.transparency_entries on a policy basis,
e.g. requiring at least one transparency log entry or a threshold of
entries. When verifying transparency entries, the verifier MUST confirm
that the inclusion time for each entry lies within the signing
certificate's validity period.

Security Implications

This PEP is primarily "mechanical" in nature; it provides layouts for
structuring and serving verifiable digital attestations without
specifying higher level security "policies" around attestation validity,
thresholds between attestations, and so forth.

Cryptographic agility in attestations

Algorithmic agility is a common source of exploitable vulnerabilities in
cryptographic schemes. This PEP limits algorithmic agility in two ways:

-   All algorithms are specified in a single suite, rather than a
    geometric collection of parameters. This makes it impossible (for
    example) for an attacker to select a strong signature algorithm with
    a weak hash function, compromising the scheme as a whole.
-   Attestation objects are versioned, and may only contain the
    algorithmic suite specified for their version. If a specific suite
    is considered insecure in the future, clients may choose to blanket
    reject or qualify verifications of attestations that contain that
    suite.

Index trust

This PEP does not increase (or decrease) trust in the index itself: the
index is still effectively trusted to honestly deliver unmodified
package distributions, since a dishonest index capable of modifying
package contents could also dishonestly modify or omit package
attestations. As a result, this PEP's presumption of index trust is
equivalent to the unstated presumption with earlier mechanisms, like PGP
and wheel signatures.

This PEP does not preclude or exclude future index trust mechanisms,
such as PEP 458 and/or PEP 480.

Recommendations

This PEP recommends, but does not mandate, that attestation objects
contain one or more verifiable sources of signed time that corroborate
the signing certificate's claimed validity period. Indices that
implement this PEP may choose to strictly enforce this requirement.

Appendix 1: Example Trusted Publisher Representation

This appendix provides a fictional example of a publisher key within a
simple JSON API project.files[].provenance listing:

    "publisher": {
        "kind": "GitHub",
        "claims": {
            "ref": "refs/tags/v1.0.0",
            "sha": "da39a3ee5e6b4b0d3255bfef95601890afd80709"
        },
        "repository_name": "HolyGrail",
        "repository_owner": "octocat",
        "repository_owner_id": "1",
        "workflow_filename": "publish.yml",
        "environment": null
    }

Appendix 2: Data models for Transparency Log Entries

This appendix contains pseudocoded data models for transparency log
entries in attestation objects. Each transparency log entry serves as a
source of signed inclusion time, and can be verified either online or
offline.

    @dataclass
    class TransparencyLogEntry:
        log_index: int
        """
        The global index of the log entry, used when querying the log.
        """

        log_id: str
        """
        An opaque, unique identifier for the log.
        """

        entry_kind: str
        """
        The kind (type) of log entry.
        """

        entry_version: str
        """
        The version of the log entry's submitted format.
        """

        integrated_time: int
        """
        The UNIX timestamp from the log from when the entry was persisted.
        """

        inclusion_proof: InclusionProof
        """
        The actual inclusion proof of the log entry.
        """

    @dataclass
    class InclusionProof:
        log_index: int
        """
        The index of the entry in the tree it was written to.
        """

        root_hash: str
        """
        The digest stored at the root of the Merkle tree at the time of proof
        generation.
        """

        tree_size: int
        """
        The size of the Merkle tree at the time of proof generation.
        """

        hashes: list[str]
        """
        A list of hashes required to complete the inclusion proof, sorted
        in order from leaf to root. The leaf and root hashes are not themselves
        included in this list; the root is supplied via `root_hash` and the client
        must calculate the leaf hash.
        """

        checkpoint: str
        """
        The signed tree head's signature, at the time of proof generation.
        """

        cosigned_checkpoints: list[str]
        """
        Cosigned checkpoints from zero or more log witnesses.
        """

Appendix 3: Simple JSON API size considerations

A previous draft of this PEP required embedding each
provenance object <provenance-object> directly into its appropriate part
of the JSON Simple API.

The current version of this PEP embeds the SHA-256 digest of the
provenance object instead. This is done for size and network bandwidth
consideration reasons:

1.  We estimate the typical size of an attestation object to be
    approximately 5.3 KB of JSON.
2.  We conservatively estimate that indices eventually host around 3
    attestations per release file, or approximately 15.9 KB of JSON per
    combined provenance object.
3.  As of May 2024, the average project on PyPI has approximately 21
    release files. We conservatively expect this average to increase
    over time.
4.  Combined, these numbers imply that a typical project might expect to
    host between 60 and 70 attestations, or approximately 339 KB of
    additional JSON in its "project detail" endpoint.

These numbers are significantly worse in "pathological" cases, where
projects have hundreds or thousands of releases and/or dozens of files
per release.

Appendix 4: Example attestation statement

Given a source distribution sampleproject-1.2.3.tar.gz with a SHA-256
digest of
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855, the
following is an appropriate in-toto Statement, as a JSON object:

    {
      "_type": "https://in-toto.io/Statement/v1",
      "subject": [
        {
          "name": "sampleproject-1.2.3.tar.gz",
          "digest": {"sha256": "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"}
        }
      ],
      "predicateType": "https://some-arbitrary-predicate.example.com/v1",
      "predicate": {
        "something-else": "foo"
      }
    }

Copyright

This document is placed in the public domain or under the
CC0-1.0-Universal license, whichever is more permissive.


text:
PEP: 238 Title: Changing the Division Operator Author: Moshe Zadka
<EMAIL_ADDRESS>Guido van Rossum<EMAIL_ADDRESS>Status:
Final Type: Standards Track Content-Type: text/x-rst Created:
11-Mar-2001 Python-Version: 2.2 Post-History: 16-Mar-2001, 26-Jul-2001,
27-Jul-2001

Abstract

The current division (/) operator has an ambiguous meaning for numerical
arguments: it returns the floor of the mathematical result of division
if the arguments are ints or longs, but it returns a reasonable
approximation of the division result if the arguments are floats or
complex. This makes expressions expecting float or complex results
error-prone when integers are not expected but possible as inputs.

We propose to fix this by introducing different operators for different
operations: x/y to return a reasonable approximation of the mathematical
result of the division ("true division"), x//y to return the floor
("floor division"). We call the current, mixed meaning of x/y "classic
division".

Because of severe backwards compatibility issues, not to mention a major
flamewar on c.l.py, we propose the following transitional measures
(starting with Python 2.2):

-   Classic division will remain the default in the Python 2.x series;
    true division will be standard in Python 3.0.
-   The // operator will be available to request floor division
    unambiguously.
-   The future division statement, spelled
    from __future__ import division, will change the / operator to mean
    true division throughout the module.
-   A command line option will enable run-time warnings for classic
    division applied to int or long arguments; another command line
    option will make true division the default.
-   The standard library will use the future division statement and the
    // operator when appropriate, so as to completely avoid classic
    division.

Motivation

The classic division operator makes it hard to write numerical
expressions that are supposed to give correct results from arbitrary
numerical inputs. For all other operators, one can write down a formula
such as x*y**2 + z, and the calculated result will be close to the
mathematical result (within the limits of numerical accuracy, of course)
for any numerical input type (int, long, float, or complex). But
division poses a problem: if the expressions for both arguments happen
to have an integral type, it implements floor division rather than true
division.

The problem is unique to dynamically typed languages: in a statically
typed language like C, the inputs, typically function arguments, would
be declared as double or float, and when a call passes an integer
argument, it is converted to double or float at the time of the call.
Python doesn't have argument type declarations, so integer arguments can
easily find their way into an expression.

The problem is particularly pernicious since ints are perfect
substitutes for floats in all other circumstances: math.sqrt(2) returns
the same value as math.sqrt(2.0), 3.14*100 and 3.14*100.0 return the
same value, and so on. Thus, the author of a numerical routine may only
use floating point numbers to test his code, and believe that it works
correctly, and a user may accidentally pass in an integer input value
and get incorrect results.

Another way to look at this is that classic division makes it difficult
to write polymorphic functions that work well with either float or int
arguments; all other operators already do the right thing. No algorithm
that works for both ints and floats has a need for truncating division
in one case and true division in the other.

The correct work-around is subtle: casting an argument to float() is
wrong if it could be a complex number; adding 0.0 to an argument doesn't
preserve the sign of the argument if it was minus zero. The only
solution without either downside is multiplying an argument (typically
the first) by 1.0. This leaves the value and sign unchanged for float
and complex, and turns int and long into a float with the corresponding
value.

It is the opinion of the authors that this is a real design bug in
Python, and that it should be fixed sooner rather than later. Assuming
Python usage will continue to grow, the cost of leaving this bug in the
language will eventually outweigh the cost of fixing old code -- there
is an upper bound to the amount of code to be fixed, but the amount of
code that might be affected by the bug in the future is unbounded.

Another reason for this change is the desire to ultimately unify
Python's numeric model. This is the subject of PEP 228 (which is
currently incomplete). A unified numeric model removes most of the
user's need to be aware of different numerical types. This is good for
beginners, but also takes away concerns about different numeric behavior
for advanced programmers. (Of course, it won't remove concerns about
numerical stability and accuracy.)

In a unified numeric model, the different types (int, long, float,
complex, and possibly others, such as a new rational type) serve mostly
as storage optimizations, and to some extent to indicate orthogonal
properties such as inexactness or complexity. In a unified model, the
integer 1 should be indistinguishable from the floating point number 1.0
(except for its inexactness), and both should behave the same in all
numeric contexts. Clearly, in a unified numeric model, if a==b and c==d,
a/c should equal b/d (taking some liberties due to rounding for inexact
numbers), and since everybody agrees that 1.0/2.0 equals 0.5, 1/2 should
also equal 0.5. Likewise, since 1//2 equals zero, 1.0//2.0 should also
equal zero.

Variations

Aesthetically, x//y doesn't please everyone, and hence several
variations have been proposed. They are addressed here:

-   x div y. This would introduce a new keyword. Since div is a popular
    identifier, this would break a fair amount of existing code, unless
    the new keyword was only recognized under a future division
    statement. Since it is expected that the majority of code that needs
    to be converted is dividing integers, this would greatly increase
    the need for the future division statement. Even with a future
    statement, the general sentiment against adding new keywords unless
    absolutely necessary argues against this.
-   div(x, y). This makes the conversion of old code much harder.
    Replacing x/y with x//y or x div y can be done with a simple query
    replace; in most cases the programmer can easily verify that a
    particular module only works with integers so all occurrences of x/y
    can be replaced. (The query replace is still needed to weed out
    slashes occurring in comments or string literals.) Replacing x/y
    with div(x, y) would require a much more intelligent tool, since the
    extent of the expressions to the left and right of the / must be
    analyzed before the placement of the div( and ) part can be decided.
-   x \ y. The backslash is already a token, meaning line continuation,
    and in general it suggests an escape to Unix eyes. In addition (this
    due to Terry Reedy) this would make things like eval("x\y") harder
    to get right.

Alternatives

In order to reduce the amount of old code that needs to be converted,
several alternative proposals have been put forth. Here is a brief
discussion of each proposal (or category of proposals). If you know of
an alternative that was discussed on c.l.py that isn't mentioned here,
please mail the second author.

-   Let / keep its classic semantics; introduce // for true division.
    This still leaves a broken operator in the language, and invites to
    use the broken behavior. It also shuts off the road to a unified
    numeric model a la PEP 228.
-   Let int division return a special "portmanteau" type that behaves as
    an integer in integer context, but like a float in a float context.
    The problem with this is that after a few operations, the int and
    the float value could be miles apart, it's unclear which value
    should be used in comparisons, and of course many contexts (like
    conversion to string) don't have a clear integer or float
    preference.
-   Use a directive to use specific division semantics in a module,
    rather than a future statement. This retains classic division as a
    permanent wart in the language, requiring future generations of
    Python programmers to be aware of the problem and the remedies.
-   Use from __past__ import division to use classic division semantics
    in a module. This also retains the classic division as a permanent
    wart, or at least for a long time (eventually the past division
    statement could raise an ImportError).
-   Use a directive (or some other way) to specify the Python version
    for which a specific piece of code was developed. This requires
    future Python interpreters to be able to emulate exactly several
    previous versions of Python, and moreover to do so for multiple
    versions within the same interpreter. This is way too much work. A
    much simpler solution is to keep multiple interpreters installed.
    Another argument against this is that the version directive is
    almost always overspecified: most code written for Python X.Y, works
    for Python X.(Y-1) and X.(Y+1) as well, so specifying X.Y as a
    version is more constraining than it needs to be. At the same time,
    there's no way to know at which future or past version the code will
    break.

API Changes

During the transitional phase, we have to support three division
operators within the same program: classic division (for / in modules
without a future division statement), true division (for / in modules
with a future division statement), and floor division (for //). Each
operator comes in two flavors: regular, and as an augmented assignment
operator (/= or //=).

The names associated with these variations are:

-   Overloaded operator methods:

        __div__(), __floordiv__(), __truediv__();
        __idiv__(), __ifloordiv__(), __itruediv__().

-   Abstract API C functions:

        PyNumber_Divide(), PyNumber_FloorDivide(),
        PyNumber_TrueDivide();

        PyNumber_InPlaceDivide(), PyNumber_InPlaceFloorDivide(),
        PyNumber_InPlaceTrueDivide().

-   Byte code opcodes:

        BINARY_DIVIDE, BINARY_FLOOR_DIVIDE, BINARY_TRUE_DIVIDE;
        INPLACE_DIVIDE, INPLACE_FLOOR_DIVIDE, INPLACE_TRUE_DIVIDE.

-   PyNumberMethod slots:

        nb_divide, nb_floor_divide, nb_true_divide,
        nb_inplace_divide, nb_inplace_floor_divide,
        nb_inplace_true_divide.

The added PyNumberMethod slots require an additional flag in tp_flags;
this flag will be named Py_TPFLAGS_HAVE_NEWDIVIDE and will be included
in Py_TPFLAGS_DEFAULT.

The true and floor division APIs will look for the corresponding slots
and call that; when that slot is NULL, they will raise an exception.
There is no fallback to the classic divide slot.

In Python 3.0, the classic division semantics will be removed; the
classic division APIs will become synonymous with true division.

Command Line Option

The -Q command line option takes a string argument that can take four
values: old, warn, warnall, or new. The default is old in Python 2.2 but
will change to warn in later 2.x versions. The old value means the
classic division operator acts as described. The warn value means the
classic division operator issues a warning (a DeprecationWarning using
the standard warning framework) when applied to ints or longs. The
warnall value also issues warnings for classic division when applied to
floats or complex; this is for use by the fixdiv.py conversion script
mentioned below. The new value changes the default globally so that the
/ operator is always interpreted as true division. The new option is
only intended for use in certain educational environments, where true
division is required, but asking the students to include the future
division statement in all their code would be a problem.

This option will not be supported in Python 3.0; Python 3.0 will always
interpret / as true division.

(This option was originally proposed as -D, but that turned out to be an
existing option for Jython, hence the Q -- mnemonic for Quotient. Other
names have been proposed, like -Qclassic, -Qclassic-warn, -Qtrue, or
-Qold_division etc.; these seem more verbose to me without much
advantage. After all the term classic division is not used in the
language at all (only in the PEP), and the term true division is rarely
used in the language -- only in __truediv__.)

Semantics of Floor Division

Floor division will be implemented in all the Python numeric types, and
will have the semantics of:

    a // b == floor(a/b)

except that the result type will be the common type into which a and b
are coerced before the operation.

Specifically, if a and b are of the same type, a//b will be of that type
too. If the inputs are of different types, they are first coerced to a
common type using the same rules used for all other arithmetic
operators.

In particular, if a and b are both ints or longs, the result has the
same type and value as for classic division on these types (including
the case of mixed input types; int//long and long//int will both return
a long).

For floating point inputs, the result is a float. For example:

    3.5//2.0 == 1.0

For complex numbers, // raises an exception, since floor() of a complex
number is not allowed.

For user-defined classes and extension types, all semantics are up to
the implementation of the class or type.

Semantics of True Division

True division for ints and longs will convert the arguments to float and
then apply a float division. That is, even 2/1 will return a
float (2.0), not an int. For floats and complex, it will be the same as
classic division.

The 2.2 implementation of true division acts as if the float type had
unbounded range, so that overflow doesn't occur unless the magnitude of
the mathematical result is too large to represent as a float. For
example, after x = 1L << 40000, float(x) raises OverflowError (note that
this is also new in 2.2: previously the outcome was platform-dependent,
most commonly a float infinity). But x/x returns 1.0 without exception,
while x/1 raises OverflowError.

Note that for int and long arguments, true division may lose
information; this is in the nature of true division (as long as
rationals are not in the language). Algorithms that consciously use
longs should consider using //, as true division of longs retains no
more than 53 bits of precision (on most platforms).

If and when a rational type is added to Python (see PEP 239), true
division for ints and longs should probably return a rational. This
avoids the problem with true division of ints and longs losing
information. But until then, for consistency, float is the only choice
for true division.

The Future Division Statement

If from __future__ import division is present in a module, or if -Qnew
is used, the / and /= operators are translated to true division opcodes;
otherwise they are translated to classic division (until Python 3.0
comes along, where they are always translated to true division).

The future division statement has no effect on the recognition or
translation of // and //=.

See PEP 236 for the general rules for future statements.

(It has been proposed to use a longer phrase, like true_division or
modern_division. These don't seem to add much information.)

Open Issues

We expect that these issues will be resolved over time, as more feedback
is received or we gather more experience with the initial
implementation.

-   It has been proposed to call // the quotient operator, and the /
    operator the ratio operator. I'm not sure about this -- for some
    people quotient is just a synonym for division, and ratio suggests
    rational numbers, which is wrong. I prefer the terminology to be
    slightly awkward if that avoids unambiguity. Also, for some folks
    quotient suggests truncation towards zero, not towards infinity as
    floor division says explicitly.
-   It has been argued that a command line option to change the default
    is evil. It can certainly be dangerous in the wrong hands: for
    example, it would be impossible to combine a 3rd party library
    package that requires -Qnew with another one that requires -Qold.
    But I believe that the VPython folks need a way to enable true
    division by default, and other educators might need the same. These
    usually have enough control over the library packages available in
    their environment.
-   For classes to have to support all three of __div__(),
    __floordiv__() and __truediv__() seems painful; and what to do in
    3.0? Maybe we only need __div__() and __floordiv__(), or maybe at
    least true division should try __truediv__() first and __div__()
    second.

Resolved Issues

-   Issue: For very large long integers, the definition of true division
    as returning a float causes problems, since the range of Python
    longs is much larger than that of Python floats. This problem will
    disappear if and when rational numbers are supported.

    Resolution: For long true division, Python uses an internal float
    type with native double precision but unbounded range, so that
    OverflowError doesn't occur unless the quotient is too large to
    represent as a native double.

-   Issue: In the interim, maybe the long-to-float conversion could be
    made to raise OverflowError if the long is out of range.

    Resolution: This has been implemented, but, as above, the magnitude
    of the inputs to long true division doesn't matter; only the
    magnitude of the quotient matters.

-   Issue: Tim Peters will make sure that whenever an in-range float is
    returned, decent precision is guaranteed.

    Resolution: Provided the quotient of long true division is
    representable as a float, it suffers no more than 3 rounding errors:
    one each for converting the inputs to an internal float type with
    native double precision but unbounded range, and one more for the
    division. However, note that if the magnitude of the quotient is too
    small to represent as a native double, 0.0 is returned without
    exception ("silent underflow").

FAQ

When will Python 3.0 be released?

  We don't plan that long ahead, so we can't say for sure. We want to
  allow at least two years for the transition. If Python 3.0 comes out
  sooner, we'll keep the 2.x line alive for backwards compatibility
  until at least two years from the release of Python 2.2. In practice,
  you will be able to continue to use the Python 2.x line for several
  years after Python 3.0 is released, so you can take your time with the
  transition. Sites are expected to have both Python 2.x and Python 3.x
  installed simultaneously.

Why isn't true division called float division?

  Because I want to keep the door open to possibly introducing rationals
  and making 1/2 return a rational rather than a float. See PEP 239.

Why is there a need for __truediv__ and __itruediv__?

  We don't want to make user-defined classes second-class citizens.
  Certainly not with the type/class unification going on.

How do I write code that works under the classic rules as well as under the new rules without using // or a future division statement?

  Use x*1.0/y for true division, divmod(x, y) (PEP 228) for int
  division. Especially the latter is best hidden inside a function. You
  may also write float(x)/y for true division if you are sure that you
  don't expect complex numbers. If you know your integers are never
  negative, you can use int(x/y) -- while the documentation of int()
  says that int() can round or truncate depending on the C
  implementation, we know of no C implementation that doesn't truncate,
  and we're going to change the spec for int() to promise truncation.
  Note that classic division (and floor division) round towards negative
  infinity, while int() rounds towards zero, giving different answers
  for negative numbers.

How do I specify the division semantics for input(), compile(), execfile(), eval() and exec?

  They inherit the choice from the invoking module. PEP 236 now lists
  this as a resolved problem, referring to PEP 264.

What about code compiled by the codeop module?

  This is dealt with properly; see PEP 264.

Will there be conversion tools or aids?

  Certainly. While these are outside the scope of the PEP, I should
  point out two simple tools that will be released with Python 2.2a3:
  Tools/scripts/finddiv.py finds division operators (slightly smarter
  than grep /) and Tools/scripts/fixdiv.py can produce patches based on
  run-time analysis.

Why is my question not answered here?

  Because we weren't aware of it. If it's been discussed on c.l.py and
  you believe the answer is of general interest, please notify the
  second author. (We don't have the time or inclination to answer every
  question sent in private email, hence the requirement that it be
  discussed on c.l.py first.)

Implementation

Essentially everything mentioned here is implemented in CVS and will be
released with Python 2.2a3; most of it was already released with Python
2.2a2.

Copyright

This document has been placed in the public domain.