BUG #15580: ALTER TABLE with new column and ADD PRIMARY KEY throws spurious "column contains null values"

The following bug has been logged on the website:

Bug reference:      15580
Logged by:          Allison Kaptur
Email address:      allison.kaptur@gmail.com
PostgreSQL version: 9.6.2
Operating system:   Any
Description:        

An ALTER TABLE that both (a) adds a primary key on an existing column and
(b) adds a new not-null column fails with "column 'new_col' contains null
values".

Tom Lane helpfully boiled down my original problem to a smaller repro:
regression=# create table t1 (a int);
CREATE TABLE
regression=# insert into t1 values(1);
INSERT 0 1
regression=# alter table t1 add column b float8 not null default random(),
add primary key(a);
ERROR:  column "b" contains null values

Tom adds (on pgsql-general):
> It fails like that as far back as I tried (8.4).  I'm guessing that
we're
doing the ALTER steps in the wrong order, but haven't looked closer than
that.

> Interestingly, in v11 and HEAD it works if you use a constant default,
suggesting that the fast-default feature is at least adjacent to the
problem.


Two workarounds that do not trigger the bug:
1. Setting NOT NULL in a separate step from adding the column
ALTER TABLE t1
    ADD COLUMN b int UNIQUE DEFAULT random(),
    ADD PRIMARY KEY (a),
    ALTER COLUMN b SET NOT NULL;

2. Splitting the command into two ALTER TABLE statements
ALTER TABLE t1
    ADD COLUMN b int UNIQUE NOT NULL DEFAULT random();
ALTER TABLE new_table
    ADD PRIMARY KEY (a);

These two workarounds leave me with the same theory as Tom: postgres seems
to be rewriting the order of the ALTER steps so that NOT NULL is applied to
the new column before the default values are supplied.