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(dot)kaptur(at)gmail(dot)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.