Window tree and window's internal height

Window tree and window's internal height

[Eli Zaretskii]

Martin, I'd like your opinion on the following two issues.  (Anyone
else who has an opinion is welcome to chime in.)

First, we have this in the ELisp manual:

     A minibuffer window (*note Minibuffer Windows::) is not part of its
  frame’s window tree unless the frame is a minibuffer-only frame.
  Nonetheless, most of the functions in this section accept the minibuffer
  window as an argument.  Also, the function ‘window-tree’ described at
  the end of this section lists the minibuffer window alongside the actual
  window tree.

The first sentence is incorrect, isn't it?  Because Emacs disagrees:

  emacs -Q
  M-: (window-next-sibling) RET
   => #<window 4 on  *Minibuf-0*>

And if that sentence is incorrect, we don't need the next two
"exceptions", right?

Next, please have a look at the function window_internal_height:

  /* Return number of lines of text (not counting mode lines) in W.  */

  int
  window_internal_height (struct window *w)
  {
    int ht = w->total_lines;

    if (!MINI_WINDOW_P (w))
      {
	if (!NILP (w->parent)
	    || WINDOWP (w->contents)
	    || !NILP (w->next)
	    || !NILP (w->prev)
	    || window_wants_mode_line (w))
	  --ht;

	if (window_wants_header_line (w))
	  --ht;
      }

    return ht;
  }

I don't understand any of the conditions except window_wants_mode_line
when we decide whether to decrease the height due to the mode line.
What do the other conditions have to do with the window's height?  I
could perhaps understand the "WINDOWP (w->contents)" part, as some
kind of optimization for non-leaf windows, which assumes the default
of having the mode line, but the rest seem simply wrong, don't they?
(The WINDOWP condition is not really interesting, as I don't see any
call of this function for a non-leaf window.)

This is the immediate cause of bug#33363, which I could fix either by
a local change in try_window_id, or by modifying
window_internal_height to leave only the window_wants_mode_line
condition there.  If the latter might be unsafe, maybe I should do the
former on the release branch and the latter on master.  WDYT?

TIA

Re: Window tree and window's internal height

[martin rudalics]

 > First, we have this in the ELisp manual:
 >
 >       A minibuffer window (*note Minibuffer Windows::) is not part of its
 >    frame’s window tree unless the frame is a minibuffer-only frame.
 >    Nonetheless, most of the functions in this section accept the minibuffer
 >    window as an argument.  Also, the function ‘window-tree’ described at
 >    the end of this section lists the minibuffer window alongside the actual
 >    window tree.
 >
 > The first sentence is incorrect, isn't it?  Because Emacs disagrees:
 >
 >    emacs -Q
 >    M-: (window-next-sibling) RET
 >     => #<window 4 on  *Minibuf-0*>
 >
 > And if that sentence is incorrect, we don't need the next two
 > "exceptions", right?

Right, graph theoretically.  For a long time, however, the Elisp manual
has used the term "root", for example, in Emacs 22 as follows

      The return value is a list of the form `(ROOT MINI)', where ROOT
      represents the window tree of the frame's root window, and MINI is
      the frame's minibuffer window.

which implies that Emacs' window tree is not free but a "rooted tree"
and in a rooted tree every node except the root must have a unique
parent node.  But the minibuffer window does not have a parent so we
would have two nodes without parent.

Which means that our window tree concept per se is valid but using
'window-next-sibling' to get the minibuffer window from the root
window is an incorrect naming convention.  It's simply there because
'window-next-sibling' is a 1-to-1 reflection of the w->next field of
the window structure in window.h.

 > Next, please have a look at the function window_internal_height:
 >
 >    /* Return number of lines of text (not counting mode lines) in W.  */
 >
 >    int
 >    window_internal_height (struct window *w)
 >    {
 >      int ht = w->total_lines;
 >
 >      if (!MINI_WINDOW_P (w))
 >        {
 > 	if (!NILP (w->parent)
 > 	    || WINDOWP (w->contents)
 > 	    || !NILP (w->next)
 > 	    || !NILP (w->prev)
 > 	    || window_wants_mode_line (w))
 > 	  --ht;
 >
 > 	if (window_wants_header_line (w))
 > 	  --ht;
 >        }
 >
 >      return ht;
 >    }
 >
 > I don't understand any of the conditions except window_wants_mode_line
 > when we decide whether to decrease the height due to the mode line.
 > What do the other conditions have to do with the window's height?  I
 > could perhaps understand the "WINDOWP (w->contents)" part, as some
 > kind of optimization for non-leaf windows, which assumes the default
 > of having the mode line, but the rest seem simply wrong, don't they?
 > (The WINDOWP condition is not really interesting, as I don't see any
 > call of this function for a non-leaf window.)

Whatever these three conditions were meant for is beyond my
imagination.  window_internal_height was always off-limit for me.  I
wonder how these miscalculations would affect window_scroll_line_based
(I hardly ever use modeline-less windows) though.

 > This is the immediate cause of bug#33363, which I could fix either by
 > a local change in try_window_id, or by modifying
 > window_internal_height to leave only the window_wants_mode_line
 > condition there.  If the latter might be unsafe, maybe I should do the
 > former on the release branch and the latter on master.  WDYT?

I would call window_body_height on the release branch and on master.
And I would use window_body_height in window_scroll_line_based too.
It should then take care of dividers and horizontal scroll bars on GUI
windows as well.

martin

Re: Window tree and window's internal height

[Eli Zaretskii]

> Date: Sat, 17 Nov 2018 19:39:36 +0100
> From: martin rudalics <rudalics@gmx.at>
> CC: emacs-devel@gnu.org
> 
>  > First, we have this in the ELisp manual:
>  >
>  >       A minibuffer window (*note Minibuffer Windows::) is not part of its
>  >    frame’s window tree unless the frame is a minibuffer-only frame.
>  >    Nonetheless, most of the functions in this section accept the minibuffer
>  >    window as an argument.  Also, the function ‘window-tree’ described at
>  >    the end of this section lists the minibuffer window alongside the actual
>  >    window tree.
>  >
>  > The first sentence is incorrect, isn't it?  Because Emacs disagrees:
>  >
>  >    emacs -Q
>  >    M-: (window-next-sibling) RET
>  >     => #<window 4 on  *Minibuf-0*>
>  >
>  > And if that sentence is incorrect, we don't need the next two
>  > "exceptions", right?
> 
> Right, graph theoretically.  For a long time, however, the Elisp manual
> has used the term "root", for example, in Emacs 22 as follows
> 
>       The return value is a list of the form `(ROOT MINI)', where ROOT
>       represents the window tree of the frame's root window, and MINI is
>       the frame's minibuffer window.
> 
> which implies that Emacs' window tree is not free but a "rooted tree"
> and in a rooted tree every node except the root must have a unique
> parent node.  But the minibuffer window does not have a parent so we
> would have two nodes without parent.

So maybe we should simply say that the mini-window doesn't have a
parent, instead of what we say now?

> Which means that our window tree concept per se is valid but using
> 'window-next-sibling' to get the minibuffer window from the root
> window is an incorrect naming convention.  It's simply there because
> 'window-next-sibling' is a 1-to-1 reflection of the w->next field of
> the window structure in window.h.

Looking at w->next _was_ what tripped me in the first place: I didn't
expect a sole window on a TTY frame to have a non-nil object pointed
by its 'next' pointer.  I don't think we should assume that the ELisp
manual is only for people who work on the Lisp level.

>  >    int
>  >    window_internal_height (struct window *w)
>  >    {
>  >      int ht = w->total_lines;
>  >
>  >      if (!MINI_WINDOW_P (w))
>  >        {
>  > 	if (!NILP (w->parent)
>  > 	    || WINDOWP (w->contents)
>  > 	    || !NILP (w->next)
>  > 	    || !NILP (w->prev)
>  > 	    || window_wants_mode_line (w))
>  > 	  --ht;
>  >
>  > 	if (window_wants_header_line (w))
>  > 	  --ht;
>  >        }
>  >
>  >      return ht;
>  >    }
>  >
>  > I don't understand any of the conditions except window_wants_mode_line
>  > when we decide whether to decrease the height due to the mode line.
>  > What do the other conditions have to do with the window's height?  I
>  > could perhaps understand the "WINDOWP (w->contents)" part, as some
>  > kind of optimization for non-leaf windows, which assumes the default
>  > of having the mode line, but the rest seem simply wrong, don't they?
>  > (The WINDOWP condition is not really interesting, as I don't see any
>  > call of this function for a non-leaf window.)
> 
> Whatever these three conditions were meant for is beyond my
> imagination.

Well, I guess that answers my question: it's simply a very old bug.

> window_internal_height was always off-limit for me.  I
> wonder how these miscalculations would affect window_scroll_line_based

I don't think they do, because the result is either used as a limit to
clip some value, or for computing half the window-full, which errs by
half a line half of the time anyway (due to integer division).

> (I hardly ever use modeline-less windows) though.

Sounds like almost no one does, or we would have heard about bug#33363
and its ilk a long time ago.

>  > This is the immediate cause of bug#33363, which I could fix either by
>  > a local change in try_window_id, or by modifying
>  > window_internal_height to leave only the window_wants_mode_line
>  > condition there.  If the latter might be unsafe, maybe I should do the
>  > former on the release branch and the latter on master.  WDYT?
> 
> I would call window_body_height on the release branch and on master.

window_body_height attempts to calculate the mode-line and header-line
heights in pixels, which might be expensive and if so entirely a waste
of CPU cycles on TTY frames.  But I guess this indirectly answers my
question, because my proposed change in window_internal_height will
make it the exact equivalent of window_body_height for TTY frames.  So
I think I will make that change on the release branch.

> And I would use window_body_height in window_scroll_line_based too.
> It should then take care of dividers and horizontal scroll bars on GUI
> windows as well.

window_scroll_line_based is never used on GUI frames, and dividers and
scroll bars always have exactly zero size on TTY frames.  Right?

I see only one GUI client of window_internal_height: ns-win.el, where
it calls compute-motion.  But it calls that function in a way that
doesn't trigger the call to window_internal_height, so I think we are
safe.  However, maybe ns-win.el should switch to using
window-body-height instead.

Thanks.

Re: Window tree and window's internal height

[martin rudalics]

 >>   >       A minibuffer window (*note Minibuffer Windows::) is not part of its
 >>   >    frame’s window tree unless the frame is a minibuffer-only frame.
 >>   >    Nonetheless, most of the functions in this section accept the minibuffer
 >>   >    window as an argument.  Also, the function ‘window-tree’ described at
 >>   >    the end of this section lists the minibuffer window alongside the actual
 >>   >    window tree.
[...]
 > So maybe we should simply say that the mini-window doesn't have a
 > parent, instead of what we say now?

We can do that.  But that would not remove or explain the fact that
the minibuffer is the next sibling of the root window and the root
window the previous sibling of the minibuffer window.  We could add a
sentence like "For convenience, the function `window-next-sibling',
when invoked with the root window as argument, returns its frame's
minibuffer window if the frame has a minibuffer window and is not a
minibuffer-only frame." unless it's even more confusing.

 > Looking at w->next _was_ what tripped me in the first place: I didn't
 > expect a sole window on a TTY frame to have a non-nil object pointed
 > by its 'next' pointer.

I miss you here.  The display code is the major client of this trick
and I suppose it has been invented only to make all these "while (w)"
constructs in dispnew.c seamlessly work on the minibuffer window too.
I don't like it much because when I want to display a "permanent"
minibuffer window at the top of the frame, it must be still the "next"
sibling of the root window.  Worse even - I cannot easily display the
echo area at the top of the frame and the minibuffer at its bottom in
two (semi-)permanent windows.

 > I don't think we should assume that the ELisp
 > manual is only for people who work on the Lisp level.

Section E.9.2 Window Internals is not very enlightening either in this
regard (and it hasn't seen an update for decades).

 > Well, I guess that answers my question: it's simply a very old bug.

A window that has no parent, no next and no prev is alone on its frame
- either a minibuffer-less frame or a minibuffer only frame.  So the
tests allow to conclude that the window is not alone on its frame.
But this shouldn't imply that the window has a modeline.  Maybe in the
old days it did.

 >> I would call window_body_height on the release branch and on master.
 >
 > window_body_height attempts to calculate the mode-line and header-line
 > heights in pixels, which might be expensive and if so entirely a waste
 > of CPU cycles on TTY frames.

Right.

 > But I guess this indirectly answers my
 > question, because my proposed change in window_internal_height will
 > make it the exact equivalent of window_body_height for TTY frames.  So
 > I think I will make that change on the release branch.
 >
 >> And I would use window_body_height in window_scroll_line_based too.
 >> It should then take care of dividers and horizontal scroll bars on GUI
 >> windows as well.
 >
 > window_scroll_line_based is never used on GUI frames,

I wasn't aware of that.  I always thought the comment

   /* If we must, use the pixel-based version which is much slower than
      the line-based one but can handle varying line heights.  */

means that we would allow for some sort of line based scrolling on GUI
frames.

 > and dividers and
 > scroll bars always have exactly zero size on TTY frames.  Right?

Right.

martin

Re: Window tree and window's internal height

[Eli Zaretskii]

> Date: Sun, 18 Nov 2018 20:40:43 +0100
> From: martin rudalics <rudalics@gmx.at>
> CC: emacs-devel@gnu.org
> 
>  >>   >       A minibuffer window (*note Minibuffer Windows::) is not part of its
>  >>   >    frame’s window tree unless the frame is a minibuffer-only frame.
>  >>   >    Nonetheless, most of the functions in this section accept the minibuffer
>  >>   >    window as an argument.  Also, the function ‘window-tree’ described at
>  >>   >    the end of this section lists the minibuffer window alongside the actual
>  >>   >    window tree.
> [...]
>  > So maybe we should simply say that the mini-window doesn't have a
>  > parent, instead of what we say now?
> 
> We can do that.  But that would not remove or explain the fact that
> the minibuffer is the next sibling of the root window and the root
> window the previous sibling of the minibuffer window.  We could add a
> sentence like "For convenience, the function `window-next-sibling',
> when invoked with the root window as argument, returns its frame's
> minibuffer window if the frame has a minibuffer window and is not a
> minibuffer-only frame." unless it's even more confusing.

I thought of saying something like

  The minibuffer window does not have a parent window, but it
  nevertheless is a sibling of the frame's root window, and thus can
  be reached via window-next-sibling.

>  > Looking at w->next _was_ what tripped me in the first place: I didn't
>  > expect a sole window on a TTY frame to have a non-nil object pointed
>  > by its 'next' pointer.
> 
> I miss you here.  The display code is the major client of this trick

And you therefore assumed that I must remember this factoid by heart?
I don't.  I've read the description of the window tree, and thought
"this is a single window on its TTY frame, it cannot possibly have
anything non-nil pointed to by its 'next' pointer".  Oops!

> I don't like it much because when I want to display a "permanent"
> minibuffer window at the top of the frame, it must be still the "next"
> sibling of the root window.  Worse even - I cannot easily display the
> echo area at the top of the frame and the minibuffer at its bottom in
> two (semi-)permanent windows.

I guess you will need to invent one more "bastard" node in the tree
that doesn't have a parent?

>  > window_scroll_line_based is never used on GUI frames,
> 
> I wasn't aware of that.  I always thought the comment
> 
>    /* If we must, use the pixel-based version which is much slower than
>       the line-based one but can handle varying line heights.  */
> 
> means that we would allow for some sort of line based scrolling on GUI
> frames.

No.  The code is very unequivocal:

  /* If we must, use the pixel-based version which is much slower than
     the line-based one but can handle varying line heights.  */
  if (FRAME_WINDOW_P (XFRAME (XWINDOW (window)->frame)))  <<<<<<<<<<
    window_scroll_pixel_based (window, n, whole, noerror);
  else
    window_scroll_line_based (window, n, whole, noerror);

>  > and dividers and
>  > scroll bars always have exactly zero size on TTY frames.  Right?
> 
> Right.

OK, thanks.  I'll make the changes.

Re: Window tree and window's internal height

[martin rudalics]

 > I thought of saying something like
 >
 >    The minibuffer window does not have a parent window, but it
 >    nevertheless is a sibling of the frame's root window, and thus can
 >    be reached via window-next-sibling.

I'd start the sentence with "A minibuffer window that is not alone on
its frame ..." but for the rest it's fine with me.

 >> I miss you here.  The display code is the major client of this trick
 >
 > And you therefore assumed that I must remember this factoid by heart?

Indeed, I did.  Also because most of the Elisp windows code I added
swirls away this factoid by using 'window-right' and 'window-left'.

 > I don't.  I've read the description of the window tree, and thought
 > "this is a single window on its TTY frame, it cannot possibly have
 > anything non-nil pointed to by its 'next' pointer".  Oops!

So sometimes such details are important in the manual.  Still, I
wouldn't rely on the Elisp manual to tell me anything about the
underlying C structures.

Inherently, the root of each window tree is a virtual "inner frame"
window which must have at least one and at most two child windows -
the root window and the minibuffer window.  This is important for
resizing operations which have to guarantee that the heights of the
minibuffer and root window sum up to the height of the inner frame.

Since for the rest that virtual window has no importance - once set
up its child windows can never change - code for it was never written
out explicitly.  So a correct specification of our window tree concept
would have to talk about that inner frame window but then the entire
definitions of root window would have to be rewritten ...

 > I guess you will need to invent one more "bastard" node in the tree
 > that doesn't have a parent?

And make it the next sibling of the other minibuffer window.  It gives
up the idea of an "ordered" tree but since the root has a next sibling
already it's not a rooted tree anyway.

 > No.  The code is very unequivocal:
 >
 >    /* If we must, use the pixel-based version which is much slower than
 >       the line-based one but can handle varying line heights.  */
 >    if (FRAME_WINDOW_P (XFRAME (XWINDOW (window)->frame)))  <<<<<<<<<<
 >      window_scroll_pixel_based (window, n, whole, noerror);
 >    else
 >      window_scroll_line_based (window, n, whole, noerror);

The code is unequivocal, the comment leaves much room to
interpretation.

martin

Re: Window tree and window's internal height

[Eli Zaretskii]

> Date: Mon, 19 Nov 2018 10:41:03 +0100
> From: martin rudalics <rudalics@gmx.at>
> CC: emacs-devel@gnu.org
> 
>  > I thought of saying something like
>  >
>  >    The minibuffer window does not have a parent window, but it
>  >    nevertheless is a sibling of the frame's root window, and thus can
>  >    be reached via window-next-sibling.
> 
> I'd start the sentence with "A minibuffer window that is not alone on
> its frame ..." but for the rest it's fine with me.

Thanks, I used that.

>  > I don't.  I've read the description of the window tree, and thought
>  > "this is a single window on its TTY frame, it cannot possibly have
>  > anything non-nil pointed to by its 'next' pointer".  Oops!
> 
> So sometimes such details are important in the manual.  Still, I
> wouldn't rely on the Elisp manual to tell me anything about the
> underlying C structures.

Well, I turned to the manual after becoming disappointed in the
comments to 'struct window' definition...

>  > No.  The code is very unequivocal:
>  >
>  >    /* If we must, use the pixel-based version which is much slower than
>  >       the line-based one but can handle varying line heights.  */
>  >    if (FRAME_WINDOW_P (XFRAME (XWINDOW (window)->frame)))  <<<<<<<<<<
>  >      window_scroll_pixel_based (window, n, whole, noerror);
>  >    else
>  >      window_scroll_line_based (window, n, whole, noerror);
> 
> The code is unequivocal, the comment leaves much room to
> interpretation.

I made it more clear now.

Re: Window tree and window's internal height

[martin rudalics]

 > Well, I turned to the manual after becoming disappointed in the
 > comments to 'struct window' definition...

Tell me which ones you find not useful or incomplete and I'll try to
fix them.  We should also decide what to do with the Object Internals
section of the Elisp manual - update or remove it.  I'd do the latter
because IMHO we'll be hardly able to keep it up to date unless we add
rather strong advices to window.h, buffer.h and process.h.

 >> The code is unequivocal, the comment leaves much room to
 >> interpretation.
 >
 > I made it more clear now.

It's clear now.

Thanks, martin

Re: Window tree and window's internal height

[Eli Zaretskii]

> Date: Tue, 20 Nov 2018 10:28:19 +0100
> From: martin rudalics <rudalics@gmx.at>
> CC: emacs-devel@gnu.org
> 
>  > Well, I turned to the manual after becoming disappointed in the
>  > comments to 'struct window' definition...
> 
> Tell me which ones you find not useful or incomplete and I'll try to
> fix them.

The next/prev pointers and their relation to the parent pointer and to
the 'contents' and pseudo_window_p members.  You will see that I
already added some details there, but maybe they aren't accurate
enough, or you can add more explanations.

The original problem was that when I saw this:

      if (!NILP (w->parent)
	  || WINDOWP (w->contents)
	  || !NILP (w->next)
	  || !NILP (w->prev)

I concluded that I didn't have a clear idea what each one of the tests
means, and how they differ from the following test from
window_wants_mode_line:

  return ((WINDOW_LEAF_P (w)
	   && !MINI_WINDOW_P (w)
	   && !WINDOW_PSEUDO_P (w)
	   && !EQ (window_mode_line_format, Qnone)
	   && (!NILP (window_mode_line_format)
	       || !NILP (BVAR (XBUFFER (WINDOW_BUFFER (w)), mode_line_format)))
	   && WINDOW_PIXEL_HEIGHT (w) > WINDOW_FRAME_LINE_HEIGHT (w))

> We should also decide what to do with the Object Internals
> section of the Elisp manual - update or remove it.  I'd do the latter
> because IMHO we'll be hardly able to keep it up to date unless we add
> rather strong advices to window.h, buffer.h and process.h.

Emacs is sometimes accused to be completely devoid of documentation of
its internals, something that is said to be an obstacle for people who
might otherwise try hacking Emacs on the C level.  So I think we
should keep the little of the internals documentation we have.  We
don't (or rather shouldn't) change the internals too frequently, so
the maintenance burden isn't supposed to be too heavy.

I will fix that chapter soon.

Re: Window tree and window's internal height

[Eli Zaretskii]

> Date: Tue, 20 Nov 2018 18:06:39 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: emacs-devel@gnu.org
> 
> > We should also decide what to do with the Object Internals
> > section of the Elisp manual - update or remove it.  I'd do the latter
> > because IMHO we'll be hardly able to keep it up to date unless we add
> > rather strong advices to window.h, buffer.h and process.h.
> 
> Emacs is sometimes accused to be completely devoid of documentation of
> its internals, something that is said to be an obstacle for people who
> might otherwise try hacking Emacs on the C level.  So I think we
> should keep the little of the internals documentation we have.  We
> don't (or rather shouldn't) change the internals too frequently, so
> the maintenance burden isn't supposed to be too heavy.
> 
> I will fix that chapter soon.

Done.  Feel free to add/correct if you think something needs fixing.

Re: Window tree and window's internal height

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

Thank you for helping us keep the internals documentation.
It surely has helped many people to help us maintain the C parts of Emacs.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)