Shaded nodes are externalized without shading when compiled by XeTeX

Some shaded nodes do not externalize correctly, i.e. they externalize without shading. Here's a MWE demonstrating the problem. After the first compilation, the externalized page (page 1) features a node without shading, even if the same node in the regular output (page 2) is shaded as it should be. On subsequent compilations, memoize uses the externalized picture, so the node appears without shading even in the regular output.

\documentclass{article}
\usepackage{memoize}
\usepackage{tikz}
\begin{document}

\begin{tikzpicture}
  \node[top color=white,bottom color=black!20]{This node should be shaded.};
\end{tikzpicture}

\end{document}

This issue affects a node iff the shading used by the node was not yet used as a part of the output on a regular page. That is, once a particular shading, say top color=white,bottom color=black!20, was used in some node that was already included in some page of the regular output, it will be externalized correctly. After the first compilation of the document below, the first externalized picture comes out wrong (page 1), but the second one (page 3) comes out shaded as expected.

\documentclass{article}
\usepackage{memoize}
\usepackage{tikz}
\begin{document}

\begin{tikzpicture}
  \node[top color=white,bottom color=black!20]{This node should be shaded.};
\end{tikzpicture}

\newpage

\begin{tikzpicture}
  \node[top color=white,bottom color=black!20]{This node turns out ok.};
\end{tikzpicture}

\end{document}

Analysis. When a shading is first used, PGF inserts some specials to define it. The specials are inserted as a part of the \output routine. But as memoize ships out the externalized graphics immediately (so, before the regular output), the shading is used before it is defined.

Interestingly, this leads to the problem only for XeTeX engine. It appears that this sort of "forward reference" presents no problem for pdfTeX (and LuaTeX). In particular, the problem seems to be related to the XDV -> PDF conversion. This can be observed by manually compiling the above (say, first) document in two stages:

xelatex --no-pdf test.tex
xdvipdfmx test.xdv

The second commands produces the following warning:

xdvipdfmx:warning: Error locating image file "pgfshade1"
xdvipdfmx:warning: Specified (image) object doesn't exist: pgfshade1
xdvipdfmx:warning: Interpreting special command uxobj (pdf:) failed.
xdvipdfmx:warning: >> at page="1" position="(87.6767, 28.8323)" (in PDF)
xdvipdfmx:warning: >> xxx "pdf:uxobj @pgfshade1"

If the pages are reordered during XDV -> PDF conversion, the warning disappears and the problematic node comes out as shaded.

xdvipdfmx -s 2,1 testsh.xdv

I can see two approaches towards the resolution of this issue.

Modify memoize so that externalized pages are shipped out only after their regular output counterparts are. I can see some downsides of this approach. First, the package would need to keep (an unbounded number of) boxes containing externalized graphics around until the page containing them is finnaly shipped out. Second, the logic implementing the delayed shipout could easily turn out quite complex, especially as externalized graphics might occur in floats. This complexity could easily lead to unwanted interactions with other packages, especially as implementing it would require hacking into the \output routine. A variant of this approach would keep all the externalized stuff around until the end of the document. While this would be easier to implement, it would increase the memory requirement --- I'd say that for some documents, fatally so.
Modify xdvipdfmx to properly resolve "forward references". I have no idea how doable this might be, or how it might affect the compilation time.

sasozivanovic / memoize

Shaded nodes are externalized without shading when compiled by XeTeX #1