[Weston] More discussion about weston output relative motion algorithm

[Pekka Paalanen]

On Tue, 6 May 2014 07:26:32 +0000
"Wang, Quanxian" <quanxian.wang at intel.com> wrote:

> 
> 
> > -----Original Message-----
> > From: Pekka Paalanen [mailto:ppaalanen at gmail.com]
> > Sent: Tuesday, May 6, 2014 2:36 PM
> > To: Wang, Quanxian
> > Cc: wayland-devel at lists.freedesktop.org; Jason Ekstrand
> > (jason at jlekstrand.net); Bryce W. Harrington
> > (b.harrington at samsung.com); Fu, Michael; Hardening
> > (rdp.effort at gmail.com); Kang, Jeong Seok Subject: Re: [Weston] More
> > discussion about weston output relative motion algorithm
> > 
> > On Wed, 16 Apr 2014 04:21:46 +0000
> > "Wang, Quanxian" <quanxian.wang at intel.com> wrote:
> > 
> > > Clear some definition for easy understanding.
> > > Supposed B is beside A. B maybe leftof, rightof, above, or below
> > > A. If leftof,  output(B) is the horizontal parent of A.
> > > If above, output(B) is the vertical parent of A.
> > > If rightof, output(B) is the horizontal child of A.
> > > If below, output(B) is the vertical child of A.
> > >
> > > With definition, you will be easy to set up a binary tree. But
> > > you may think some node may have two parent. The answer is no,
> > > you can have a try to move and will find it is right. Just let
> > > you know my mistakes I ever made. When you move output to be
> > > leftof or above of another, the output will take the place of
> > > another instead of really above or left of the position of
> > > another. :) After that, you will be know why one node has  one
> > > parent at most.
> > >
> > > Of course, the original layout will be one horizontal line for
> > > extended mode.
> > >
> > > If clone mode is supported, that is fine. Keep clone link for
> > > that in output structure. The algorithm will be updated with
> > > minimal. But it will be easy and based on clone mode design.
> > 
> > Hi,
> > 
> > I have nothing against an algorithm for placing outputs in Weston,
> > and it would fit Weston core. I think we would like to support all
> > kinds of layouts based on weston.ini alone, even without any
> > dynamic configuration like your proposed protocol extension.
> > 
> > However, from your algorithm description, I am not sure how it'll
> > work for hotplug or hot-unplug.
> [Wang, Quanxian] The algorithm will process all dynamic layout
> change. If you hotplug, just add one output into the tree, just call
> enable_node(A), supposed you hot-plug A. The initial design is
> inserted it into tail of master's hlink. (master is at (0,0)). When
> you hot-unplug, that means you delete this output from the tree.
> Following the algorithm, just call delete_node(A), supposed you
> hot-unplug A. the detail algorithm, you can refer to the disable_node
> algorithm in V4.  The order to take its place is clone link,
> horizontal link and vertical link. (If no clink, then hlink, still
> no, vlink) In file module/wrandr/randr_layout_algorithm.h 115  *
> Disable Node Rules: 116  *     1) The node is deleted and the place
> is replaced by others. 117  *     2) The order to take the place of
> parent: 118  *        clink, hlink and then vlink. 119  *     Others
> are the same as clean_node.
> > 
> > Let's imagine a physical setting of four monitors, arranged like
> > this:
> > 
> > ┌───┬───┐
> > │ A │ B │
> > ├───┼───┤
> > │ C │ D │
> > └───┴───┘
> > 
> > That is a 2x2 grid.

Hi,

each question I made was independent, and supposed to start from this
particulat setup. Not as a sequence of operations, but always starting
with this.

> > 
> > There are two ways to represent this in your tree structure, I
> > believe:
> > 
> > A.hlink -> B
> > A.vlink -> C
> > C.hlink -> D
> > 
> > or
> > 
> > A.hlink -> B
> > A.vlink -> C
> > B.vlink -> D
> > 
> [Wang, Quanxian] Firstly, you imagine the grid. But from the very
> beginning,  C is not present. You can do like this. a) Initial status
>  ┌───┬───┐
>  │ A │ B │
>  ├───┼───┤
>  │     │ D │
>  └───┴───┘
>  b) hot-plugged C and move C below of A
>  ┌───┬───┐
>  │ A │ B │
>  ├───┼───┤
>  │ C  │ D │
>  └───┴───┘
> Remember, since D is below of B, there will not any relation between
> C and D. Otherwise D will have two parents (horizontal C and vertical
> B).

You did not really answer the implied question. The steps you describe
above will lead to the tree:
A.hlink -> B
A.vlink -> C
B.vlink -> D

But is the other tree structure not equally valid for the same
arrangement?

So, for each question I had, I was hoping for a comparison on what
happens if the tree structure is one or the other. They would behave
differently, right?

Another question is, is that expected or not.

When a user starts to describe the monitor arrangement, he starts with
the 2x2 grid in front of him, and to him, the two different tree
structures seem equivalent. However, they will behave
differently.

> > What happens, if C is not present originally and gets hotplugged?
> [Wang, Quanxian] 
> Original status: C is not present
>  ┌───┬───┐
>  │ A │ B │
>  ├───┼───┤
>  │     │ D │
>  └───┴───┘
>  A.hlink -> B
>  B.vlink -> D
> 
> C is hot-plugged, it will go to tail of Master(A)'s hlink.
> ┌───┬───┐
>  │ A │ B │C |
>  ├───┼───┤
>  │   │ D │
>  └───┴───┘
> A.hlink -> B
> B.hlink -> C
> B.vlink -> D

What about the other version of the tree structure, where D is right-of
C?

Sure, C is not plugged in at first, but you can still have that in the
configuration. That actually becomes a problem: can you have
non-connected outputs in weston.ini as part of the output arrangement?

> > What happens, if C gets hot-unplugged? And then plugged back?
> [Wang, Quanxian] 
> C is hot-unplugged based on previous. In previous status, C has no
> any child link (clink, hlink, vlink)
>  ┌───┬───┐
>  │ A │ B │    |
>  ├───┼───┤
>  │   │ D │
>  └───┴───┘
> C is hot-plugged, it will be as before.
>  ┌───┬───┐
>  │ A │ B │C |
>  ├───┼───┤
>  │   │ D │
>  └───┴───┘

This means that C used to be below A, but then it ends up right-of B.
That sounds quite unexpected, if C was originally configured to be
below A.

> > What happens, if a user adds a new output and defines it to be
> > left-of C? Will C end up below B or will it stay below A?
> [Wang, Quanxian] 
> If a new output called E is added and define it as left-of C. It will
> do two actions. One is add, another is move. Adding:
>  ┌───┬───┐
>  │ A │ B │C | E
>  ├───┼───┤
>  │   │ D │
>  └───┴───┘
> Move: move E left of C (it will have the actions: remove E, and then
> E replace C'place, C is moving to right of E)
>  ┌───┬───┐
>  │ A │ B │E  | C
>  ├───┼───┤
>  │   │ D │
>  └───┴───┘

I did not even imagine it would work like that.

Btw the starting arrangement was supposed to be the original 2x2 grid
┌───┬───┐
│ A │ B │
├───┼───┤
│ C │ D │
└───┴───┘

And then a user adds output E left-of C, which should lead to the
arrangement below which you said cannot be realised at all.

This seems like a fundamental problem, that your internal
representation of arrangements cannot describe a situation that is
trivially created by just saying "add E left-of C" when E didn't exist
before.

Another scenario: add E left-of A. Does this keep all outputs A-D in
place, and just expand the desktop to left? I certainly would not expect
it to move all windows to the left (when outputs A-D move to the right
to make room for E).

> > What if A is wider than C; will there be a gap between C and D?
> [Wang, Quanxian] 
> You imagine
>  ┌───┬───┐
>  │ A │ B   |
>  ├───┼───┤
>  │ C  │ D │
>  └───┴───┘
> 
> A's hlink == B
> A's vlink = C
> B's vlink = D
> 
> It is possible based on C's size. It depends on A and C's width. Also
> it depends on A and B's height. Noticed that, C has no any relation
> with D. Maybe their area will be overlapped or some gap.
> 
> > 
> > Is there a behavioral difference between the two tree structures?
> > 
> > Can you realize the following arrangement?
> >     ┌───┬───┐
> >     │ A │ B │
> > ┌───┼───┼───┤
> > │ E │ C │ D │
> > └───┴───┴───┘
> [Wang, Quanxian] You could not make it. We only has one master which
> is (0,0). It is the top-left. In this case, A has y=0, but x is not 0
> and E's x =0, and y is not 0. If you want to do that, it will
> implement pos(x,y) function to move a output to defined (x,y).
> > 
> > 
> > Then an even better question is, what would the user expect?
> > Which outputs should move, and which should stay in place with
> > respect to the desktop coordinate system (global coordinates)?
> > 
> > I don't have the correct answers here. I only agree that it would
> > be nice if Weston supported more than just a horizontal line of
> > monitors. Personally I have a vertical line setup.
> > 
> > I don't even think the problem is well-defined.
> > 
> > Maybe we need completely different algorithms for
> > vertical/horizontal line vs. a grid pattern?
> > 
> > In the end, the algorithm will only compute positions for each
> > output in the global coordinate system. Quite likely no algorithm
> > will be able to realize all possible arrangements and alignments
> > (for differing output sizes) without becoming practically unusable,
> > so we would still need the option of just defining the output
> > position as coordinates in the global space.
> [Wang, Quanxian] I believe the algorithm could be implemented, you
> can add the gap or others parameter to make it happen. The only thing
> is algorithm become very complex.

very complex = practically unusable, IMHO. It will be easier for people
to figure out the coordinates with a pen and paper than to think how to
program your algorithm to do what they want.

> In this algorithm, it links all
> outputs. Maybe some has gap, maybe some has the overlapped, but you
> still can make it. It depends on what you want.

Unintended gaps are always bad, but in some configurations they cannot
be avoided, unfortunately.

Anyway, it seems like you are squashing both the configuration and the
current arrangement into the same tree structure.

I would suggest to keep the configuration directives, and apply them in
order they are written, when assigning output positions. If a
configuration directive refers to an output that is not present or
connected, assume its size is zero and just continue. When ever a
hotplug or unplug happens, delete the current configuration and start
from the first directive again.

That way, you might not even need the tree structure at all in
struct weston_output. You certainly cannot use weston_output for
storing the configuration, because weston_output does not exist for the
disconnected outputs.

How would that sound?

The only thing I am even somewhat sure of, is that the configuration
should be separated from the current arrangement. That way people can
define in weston.ini e.g. on which side VGA-1 will appear once it gets
hotplugged.

Starting from scratch, there would be a difference between defining
1)	VGA-1 left-of LVDS-1
and
2)	LVDS-1 right-of VGA-1

They both describe the same arrangement if both are connected, but
behave differently when VGA-1 is hotplugged.

In case 1, hotplugging VGA-1 makes it appear on the left of LVDS, while
all apps that were on LVDS stay on LVDS.

In case 2, apps that were on LVDS jump to VGA-1, because now VGA-1 is
the desktop anchor, and LVDS gets moved to the right.

How your dynamic configuration protocol affects all this is yet a
different matter, which I have not thought about at all.

Anyway, that's just another proposition. Anything is probably fine for
Weston, but do not make it very complex, neither in the code nor in the
configuration directives. There will always be cornercases that just
won't fit, and need to manually specify the coordinates.


Thanks,
pq