path: root/doc/context/sources/general/manuals/hybrid/hybrid-inserts.tex

% language=uk

\startcomponent hybrid-inserts

\environment hybrid-environment

\startchapter[title={Deeply nested notes}]

\startsection [title={Introduction}]

One of the mechanisms that is not on a users retina when he or she starts using
\TEX\ is \quote {inserts}. An insert is material that is entered at one point but
will appear somewhere else in the output. Footnotes for instance can be
implemented using inserts. You create a reference symbol in the running text and
put note text at the bottom of the page or at the end of a chapter or document.
But as you don't want to do that moving around of notes yourself \TEX\ provides
macro writers with the inserts mechanism that will do some of the housekeeping.
Inserts are quite clever in the sense that they are taken into account when \TEX\
splits off a page. A single insert can even be split over two or more pages.

Other examples of inserts are floats that move to the top or bottom of the page
depending on requirements and|/|or available space. Of course the macro package
is responsible for packaging such a float (for instance an image) but by finally
putting it in an insert \TEX\ itself will attempt to deal with accumulated floats
and help you move kept over floats to following pages. When the page is finally
assembled (in the output routine) the inserts for that page become available and
can be put at the spot where they belong. In the process \TEX\ has made sure that
we have the right amount of space available.

However, let's get back to notes. In \CONTEXT\ we can have many variants of them,
each taken care of by its own class of inserts. This works quite well, as long as
a note is visible for \TEX\ which means as much as: ends up in the main page
flow. Consider the following situation:

\starttyping
before \footnote{the note} after
\stoptyping

When the text is typeset, a symbol is placed directly after the word \quote
{before} and the note itself ends up at the bottom of the page. It also works
when we wrap the text in an horizontal box:

\starttyping
\hbox{before \footnote{the note} after}
\stoptyping

But it fails as soon as we go further:

\starttyping
\hbox{\hbox{before \footnote{the note} after}}
\stoptyping

Here we get the reference but no note. This also fails:

\starttyping
\vbox{before \footnote{the note} after}
\stoptyping

Can you imagine what happens if we do the following?

\starttyping
\starttabulate
\NC knuth \NC test \footnote{knuth} \input knuth \NC \NR
\NC tufte \NC test \footnote{tufte} \input tufte \NC \NR
\NC ward  \NC test \footnote{ward}  \input ward  \NC \NR
\stoptabulate
\stoptyping

This mechanism uses alignments as well as quite some boxes. The paragraphs are
nicely split over pages but still appear as boxes to \TEX\ which make inserts
invisible. Only the three symbols would remain visible. But because in \CONTEXT\
we know when notes tend to disappear, we take some provisions, and contrary to
what you might expect the notes actually do show up. However, they are flushed in
such a way that they end up on the page where the table ends. Normally this is no
big deal as we will often use local notes that end up at the end of the table
instead of the bottom of the page, but still.

The mechanism to deal with notes in \CONTEXT\ is somewhat complex at the source
code level. To mention a few properties we have to deal with:

\startitemize[packed]
\startitem Notes are collected and can be accessed any time. \stopitem
\startitem Notes are flushed either directly or delayed. \stopitem
\startitem Notes can be placed anywhere, any time, perhaps in subsets. \stopitem
\startitem Notes can be associated to lines in paragraphs. \stopitem
\startitem Notes can be placed several times with different layouts. \stopitem
\stopitemize

So, we have some control over flushing and placement, but real synchronization
between for instance table entries having notes and the note content ending up on
the same page is impossible.

In the \LUATEX\ team we have been discussing more control over inserts and we
will definitely deal with that in upcoming releases as more control is needed for
complex multi|-|column document layouts. But as we have some other priorities
these extensions have to wait.

As a prelude to them I experimented a bit with making these deeply buried inserts
visible. Of course I use \LUA\ for this as \TEX\ itself does not provide the kind
of access we need for this kind of of manipulations.

\stopsection

\startsection [title={Deep down inside}]

Say that we have the following boxed footnote. How does that end up in \LUATEX ?

\starttyping
\vbox{a\footnote{b}c}
\stoptyping

Actually it depends on the macro package but the principles remain the same. In
\LUATEX\ 0.50 and the \CONTEXT\ version used at the time of this writing we get
(nested) linked list that prints as follows:

\starttyping
<node   26 <  862 >  nil : vlist 0>
  <node  401 <  838 >  507 : hlist 1>
    <node   30 <  611 >  580 : whatsit 6>
    <node  611 <  580 >  493 : hlist 0>
    <node  580 <  493 >  653 : glyph 256>
    <node  493 <  653 >  797 : penalty 0>
    <node  653 <  797 >  424 : kern 1>
    <node  797 <  424 >  826 : hlist 2>
      <node  445 <  563 >  nil : hlist 2>
        <node  420 <  817 >  821 : whatsit 35>
        <node  817 <  821 >  nil : glyph 256>
    <node  507 <  826 > 1272 : kern 1>
    <node  826 < 1272 > 1333 : glyph 256>
    <node 1272 < 1333 >  830 : penalty 0>
    <node 1333 <  830 >  888 : glue 15>
    <node  830 <  888 >  nil : glue 9>
  <node  838 <  507 >  nil : ins 131>
\stoptyping

The numbers are internal references to the node memory pool. Each line represents
a node:

\starttyping
<node prev_index < index > next_index : type subtype>
\stoptyping

The whatsits carry directional information and the deeply nested hlist is the
note symbol. If we forget about whatsits, kerns and penalties, we can simplify
this listing to:

\starttyping
<node   26 <  862 >  nil : vlist 0>
  <node  401 <  838 >  507 : hlist 1>
    <node  580 <  493 >  653 : glyph 256>
    <node  797 <  424 >  826 : hlist 2>
      <node  445 <  563 >  nil : hlist 2>
        <node  817 <  821 >  nil : glyph 256>
    <node  826 < 1272 > 1333 : glyph 256>
  <node  838 <  507 >  nil : ins 131>
\stoptyping

So, we have a vlist (the \type {\vbox}), which has one line being a hlist. Inside
we have a glyph (the \quote{a}) followed by the raised symbol (the
\quote{\high{1}}) and next comes the second glyph (the \quote{b}). But watch how
the insert ends up at the end of the line. Although the insert will not show up
in the document, it sits there waiting to be used. So we have:

\starttyping
<node   26 <  862 >  nil : vlist 0>
  <node  401 <  838 >  507 : hlist 1>
  <node  838 <  507 >  nil : ins 131>
\stoptyping

but we need:

\starttyping
<node   26 <  862 >  nil : vlist 0>
  <node  401 <  838 >  507 : hlist 1>
<node  838 <  507 >  nil : ins 131>
\stoptyping

Now, we could use the fact that inserts end up at the end of the line, but as we
need to recursively identify them anyway, we cannot actually use this fact to
optimize the code.

In case you wonder how multiple inserts look like, here is an example:

\starttyping
\vbox{a\footnote{b}\footnote{c}d}
\stoptyping

This boils down to:

\starttyping
<node   26 < 1324 >  nil : vlist 0>
  <node  401 < 1348 >  507 : hlist 1>
  <node 1348 <  507 >  457 : ins 131>
  <node  507 <  457 >  nil : ins 131>
\stoptyping

In case you wonder what more can end up at the end, vertically adjusted material
(\type {\vadjust}) as well as marks (\type {\mark}) also get that treatment.

\starttyping
\vbox{a\footnote{b}\vadjust{c}\footnote{d}e\mark{f}}
\stoptyping

As you see, we start with the line itself, followed by a mixture of inserts and
vertically adjusted content (that will be placed before that line). This trace
also shows the list 2~levels deep.

\starttyping
<node   26 < 1324 >  nil : vlist 0>
  <node  401 < 1348 >  507 : hlist 1>
  <node 1348 <  507 >  862 : ins 131>
  <node  507 <  862 >  240 : hlist 1>
  <node  862 <  240 > 2288 : ins 131>
  <node  240 < 2288 >  nil : mark 0>
\stoptyping

Currently vadjust nodes have the same subtype as an ordinary hlist but in
\LUATEX\ versions beyond 0.50 they will have a dedicated subtype.

We can summarize the pattern of one \quote {line} in a vertical list as:

\starttyping
[hlist][insert|mark|vadjust]*[penalty|glue]+
\stoptyping

In case you wonder what happens with for instance specials, literals (and other
whatits): these end up in the hlist that holds the line. Only inserts, marks and
vadjusts migrate to the outer level, but as they stay inside the vlist, they are
not visible to the page builder unless we're dealing with the main vertical list.
Compare:

\starttyping
this is a regular paragraph possibly with inserts and they
will be visible as the lines are appended to the main
vertical list \par
\stoptyping

with:

\starttyping
but \vbox {this is a nested paragraph where inserts will
stay with the box} and not migrate here \par
\stoptyping

So much for the details; let's move on the how we can get
around this phenomenon.

\stopsection

\startsection [title={Some \LUATEX\ magic}]

The following code is just the first variant I made and \CONTEXT\ ships with a
more extensive variant. Also, in \CONTEXT\ this is part of a larger suite of
manipulative actions but it does not make much sense (at least not now) to
discuss this framework here.

We start with defining a couple of convenient shortcuts.

\starttyping
local hlist = node.id('hlist')
local vlist = node.id('vlist')
local ins   = node.id('ins')
\stoptyping

We can write a more compact solution but splitting up the functionality better
shows what we're doing. The main migration function hooks into the callback \type
{build_page}. Contrary to other callbacks that do phases in building lists and
pages this callback does not expect the head of a list as argument. Instead, we
operate directly on the additions to the main vertical list which is accessible
as \type {tex.lists.contrib_head}.

\starttyping
local deal_with_inserts -- forward reference

local function migrate_inserts(where)
    local current = tex.lists.contrib_head
    while current do
        local id = current.id
        if id == vlist or id == hlist then
            current = deal_with_inserts(current)
        end
        current = current.next
    end
end

callback.register('buildpage_filter',migrate_inserts)
\stoptyping

So, effectively we scan for vertical and horizontal lists and deal with embedded
inserts when we find them. In \CONTEXT\ the migratory function is just one of the
functions that is applied to this filter.

We locate inserts and collect them in a list with \type {first} and \type {last}
as head and tail and do so recursively. When we have run into inserts we insert
them after the horizontal or vertical list that had embedded them.

\starttyping
local locate -- forward reference

deal_with_inserts = function(head)
    local h, first, last = head.list, nil, nil
    while h do
        local id = h.id
        if id == vlist or id == hlist then
            h, first, last = locate(h,first,last)
        end
        h = h.next
    end
    if first then
        local n = head.next
        head.next = first
        first.prev = head
        if n then
            last.next = n
            n.prev = last
        end
        return last
    else
        return head
    end
end
\stoptyping

The \type {locate} function removes inserts and adds them to a new list, that is
passed on down in recursive calls and eventually is returned back to the caller.

\starttyping
locate = function(head,first,last)
    local current = head
    while current do
        local id = current.id
        if id == vlist or id == hlist then
            current.list, first, last = locate(current.list,first,last)
            current = current.next
        elseif id == ins then
            local insert = current
            head, current = node.remove(head,current)
            insert.next = nil
            if first then
                insert.prev = last
                last.next = insert
            else
                insert.prev = nil
                first = insert
            end
            last = insert
        else
            current = current.next
        end
    end
    return head, first, last
end
\stoptyping

As we can encounter the content several times in a row, it makes sense to mark
already processed inserts. This can for instance be done by setting an attribute.
Of course one has to make sure that this attribute is not used elsewhere.

\starttyping
if not node.has_attribute(current,8061) then
    node.set_attribute(current,8061,1)
    current = deal_with_inserts(current)
end
\stoptyping

or integrated:

\starttyping
local has_attribute = node.has_attribute
local set_attribute = node.set_attribute

local function migrate_inserts(where)
    local current = tex.lists.contrib_head
    while current do
        local id = current.id
        if id == vlist or id == hlist then
            if has_attribute(current,8061) then
                -- maybe some tracing message
            else
                set_attribute(current,8061,1)
                current = deal_with_inserts(current)
            end
        end
        current = current.next
    end
end

callback.register('buildpage_filter',migrate_inserts)
\stoptyping

\stopsection

\startsection [title={A few remarks}]

Surprisingly, the amount of code needed for insert migration is not that large.
This makes one wonder why \TEX\ does not provide this feature itself as it could
have saved macro writers quite some time and headaches. Performance can be a
reason, unpredictable usage and side effects might be another. Only one person
knows the answer.

In \CONTEXT\ this mechanism is built in and it can be enabled by saying:

\starttyping
\automigrateinserts
\automigratemarks
\stoptyping

As you can see here, we can also migrate marks. Future versions of \CONTEXT\ will
do this automatically and also provide some control over what classes of inserts
are moved around. We will probably overhaul the note handling mechanism a few
more times anyway as \LUATEX\ evolves and the demands from critical editions that
use many kind of notes raise.

\stopsection

\startsection [title={Summary of code}]

The following code should work in plain \TEX:

\starttyping
\directlua 0 {
local hlist         = node.id('hlist')
local vlist         = node.id('vlist')
local ins           = node.id('ins')
local has_attribute = node.has_attribute
local set_attribute = node.set_attribute

local status = 8061

local function locate(head,first,last)
    local current = head
    while current do
        local id = current.id
        if id == vlist or id == hlist then
            current.list, first, last = locate(current.list,first,last)
            current = current.next
        elseif id == ins then
            local insert = current
            head, current = node.remove(head,current)
            insert.next = nil
            if first then
                insert.prev, last.next = last, insert
            else
                insert.prev, first = nil, insert
            end
            last = insert
        else
            current = current.next
        end
    end
    return head, first, last
end

local function migrate_inserts(where)
    local current = tex.lists.contrib_head
    while current do
        local id = current.id
        if id == vlist or id == hlist and
                not has_attribute(current,status) then
            set_attribute(current,status,1)
            local h, first, last = current.list, nil, nil
            while h do
                local id = h.id
                if id == vlist or id == hlist then
                    h, first, last = locate(h,first,last)
                end
                h = h.next
            end
            if first then
                local n = current.next
                if n then
                    last.next, n.prev = n, last
                end
                current.next, first.prev = first, current
                current = last
            end
        end
        current = current.next
    end
end

callback.register('buildpage_filter', migrate_inserts)
}
\stoptyping

Alternatively you can put the code in a file and load that with:

\starttyping
\directlua {require "luatex-inserts.lua"}
\stoptyping

A simple plain test is:

\starttyping
\vbox{a\footnote{1}{1}b}
\hbox{a\footnote{2}{2}b}
\stoptyping

The first footnote only shows up when we have hooked our migrator into the
callback. A not that bad result for 60 lines of \LUA\ code.

\stopsection

\stopchapter

\stopcomponent