Strange behavior with the following recipe, using trunk:

  * ./src/emacs -Q
  * Move point up two lines
  * Insert "aaa"
  * Undo
  * Move point down two lines
  * Insert "bbb"
  * Select "bbb" from end to beginning and delete
  * Insert "bbb"
  * Go to line where "aaa" was and select the line from beginning to
    end
  * Undo in region
  * Observe:
    * "Undo in region!" is echoed in the minibuffer
    * Unexpectedly, "aaa" is not reinserted back into the buffer
    * Strangely, the selection mark at BOL moves forward three chars
  * Undo in region again
  * Observe:
    * "aaa" is reinserted, despite selection no longer covering the
      region where "aaa" was

Prior to the first undo in region, buffer-undo-list is:

  (nil (192 . 195) nil (bbb . 192) (#<marker at 141 in *scratch*> . -3)
(#<marker at 192 in *scratch*> . -3) (#<marker at 190 in *scratch*> . -3)
nil (192 . 195) (t . 0) nil (aaa . 141) nil (141 . 144) (t . 0) nil (1 .
192) (t . 0))

And after undo-make-selective-list pending-undo-list becomes:

  (nil (#<marker at 141 in *scratch*> . -3) (#<marker at 190 in *scratch*>
. -3) nil (aaa . 141) nil (141 . 144) nil)

It seems the #<marker at 141 in *scratch*> is the mark used during
selection. When bbb is deleted, the mark is recorded into undo
history, and it's still there when the selection mark has moved to
position 141 before "aaa". So:

> * Unexpectedly, "aaa" is not reinserted back into the buffer

is due to the selection mark and another marker occupying their own
change group in the filtered pending-undo-list, and that change group
is chosen for the first undo in region.

> Strangely, the selection mark at BOL moves forward three chars

is due to the -3 marker adjustment.

> * "aaa" is reinserted, despite selection no longer covering the
    region where "aaa" was

is simply due to pending-undo-list being reused for the second
consecutive undo, unaware that the selection mark was adjusted.

I haven't determined what those other two markers are. But the general
question comes up: how is the undo history meant to know about marker
relocations?

The code in adjust_markers_for_delete indicates markers are only
recorded when they would be in a deleted region or immediately before
it, so I think the only circumstance markers form their own undesired
change group in the pending-undo-list is when recorded markers
were relocated.