[Weston] More discussion about weston output relative motion algorithm

[Wang, Quanxian]

Thanks Pq's comment. Before you continue my comment, I mentioned one point.
This is output movement algorithm and it is completely different with pre-configuration of output in weston.ini.
For output, no alive, no movement.
If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration.  It is conflict with dynamic output movement.

Currently in my weston randr's patches has provided an interface to put your configure requests into one file. 

> -----Original Message-----
> From: wayland-devel [mailto:wayland-devel-bounces at lists.freedesktop.org]
> On Behalf Of Pekka Paalanen
> Sent: Tuesday, May 6, 2014 5:16 PM
> To: Wang, Quanxian
> Cc: Hardening (rdp.effort at gmail.com); Bryce W. Harrington
> (b.harrington at samsung.com); wayland-devel at lists.freedesktop.org; Jason
> Ekstrand (jason at jlekstrand.net); Kang, Jeong Seok; Fu, Michael
> Subject: Re: [Weston] More discussion about weston output relative motion
> algorithm
> 
> 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.
[Wang, Quanxian] you expected it in pre-configuration. The algorithm is designed for output alive. For output, no alive, no movement.
> 
> > >
> > > 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?
[Wang, Quanxian] Right. They behave differently because of different layout request.
You may think grid 2x2 is the same. Actual environment are not the same because of sizes of each output.
Even if they are the same as the layout. But the request from client is still not the same.
> 
> Another question is, is that expected or not.
[Wang, Quanxian] The expected is from the client layout request.
They want 
1) D is below of B
or
2) D is right of C. 
Client should be aware of that.
> 
> 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.
[Wang, Quanxian] Not equivalent. Even the layout seems like the same(not exactly the same), but the final layout will cause different thing because of each output's resolution.
Therefore we must know what the exact layout customer want.
> 
> > > 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?
[Wang, Quanxian] 
┌───┬───┐
 │ A │ B │C   |  D  |
 ├───┼───┤

> 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?
[Wang, Quanxian] Pre-configuration and algorithm are completely different. You can pre-configure it and then do it when output is available using algorithm.
But you can't do movement when output is not present. It should be a requirement for configuration instead of requirement of algorithm.
> 
> > > 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.
[Wang, Quanxian] Sorry, you unplugged C, it changes the status. When you plug it, it will change also.
Of course, your expected result is pre-defined configuration and any output change should follow this pre-defined change. It is not in algorithm. It is in weston layout configuration.
> 
> > > 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.
[Wang, Quanxian] Your imagine is important to me. Supposed you are my client, your concern will help me. Algorithm is under discussion and your comment and expected are really appreciate.
> 
> 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.
[Wang, Quanxian]  The algorithm is designed for outputs alive. When E exists, the movement happens, if no, the movement failed.
> 
> 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).
[Wang, Quanxian] If E left-of A, E will be (0,0), at the same time, A will be move right.(A'x = E's width, A'y will not be changed). Others movement follows algorithm's definition.
> 
> > > 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.
[Wang, Quanxian] Agree that.
> 
> > 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?
 [Wang, Quanxian] The pre-defined layout configuration could be stored in a place. Once output is plugged or unplugged
The change should follow the pre-definition layout configuration. It is a new requirement for weston.ini. 
But it is conflict with randr movement. It is a static configuration. If no randr, we could do that easily. :)
> 
> 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.
[Wang, Quanxian] I agree with your point.  Auto function in algorithm is provided to avoid cornercases. 

By the way, pos(x,y) function is a very flexible position for output and not implemented in randr protocol. 
It is an independent function, however will affect the output layout. Actually when you mentioned gap, I have the idea to add the gap for x or y or both into layout algorithm.
That means, it will allow space between outputs. But it will affect others movement, for example mouse. 
Pos(x,y) could be taken as the following action,
1) find the most closest output as the reference
2) Do related motion compare with it. Of course, there is a gap allowed in order to put output into exact (x,y).
> 
> 
> Thanks,
> pq
> _______________________________________________
> wayland-devel mailing list
> wayland-devel at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/wayland-devel