3 files changed, 71 insertions, 0 deletions

diff --git a/xorg-server/mi/mi.h b/xorg-server/mi/mi.h
index cf95cd79e..788f5dd54 100644
--- a/xorg-server/mi/mi.h
+++ b/xorg-server/mi/mi.h
@@ -507,6 +507,10 @@ extern _X_EXPORT void miMarkUnrealizedWindow(WindowPtr /*pChild */ ,
 extern _X_EXPORT void miSegregateChildren(WindowPtr pWin, RegionPtr pReg,
                                           int depth);
 
+extern _X_EXPORT WindowPtr miSpriteTrace(SpritePtr pSprite, int x, int y);
+
+extern _X_EXPORT WindowPtr miXYToWindow(ScreenPtr pScreen, SpritePtr pSprite, int x, int y);
+
 /* mizerarc.c */
 
 extern _X_EXPORT void miZeroPolyArc(DrawablePtr /*pDraw */ ,
diff --git a/xorg-server/mi/miscrinit.c b/xorg-server/mi/miscrinit.c
index 6aed52f51..00c15f713 100644
--- a/xorg-server/mi/miscrinit.c
+++ b/xorg-server/mi/miscrinit.c
@@ -272,6 +272,7 @@ miScreenInit(ScreenPtr pScreen, void *pbits,  /* pointer to screen bits */
     pScreen->ChangeBorderWidth = miChangeBorderWidth;
     pScreen->SetShape = miSetShape;
     pScreen->MarkUnrealizedWindow = miMarkUnrealizedWindow;
+    pScreen->XYToWindow = miXYToWindow;
 
     miSetZeroLineBias(pScreen, DEFAULTZEROLINEBIAS);
 
diff --git a/xorg-server/mi/miwindow.c b/xorg-server/mi/miwindow.c
index d9c46fd90..c6f0e5315 100644
--- a/xorg-server/mi/miwindow.c
+++ b/xorg-server/mi/miwindow.c
@@ -57,6 +57,7 @@ SOFTWARE.
 #include "scrnintstr.h"
 #include "pixmapstr.h"
 #include "mivalidate.h"
+#include "inputstr.h"
 
 void
 miClearToBackground(WindowPtr pWin,
@@ -758,3 +759,68 @@ miSegregateChildren(WindowPtr pWin, RegionPtr pReg, int depth)
             miSegregateChildren(pChild, pReg, depth);
     }
 }
+
+WindowPtr
+miSpriteTrace(SpritePtr pSprite, int x, int y)
+{
+    WindowPtr pWin;
+    BoxRec box;
+
+    pWin = DeepestSpriteWin(pSprite);
+    while (pWin) {
+        if ((pWin->mapped) &&
+            (x >= pWin->drawable.x - wBorderWidth(pWin)) &&
+            (x < pWin->drawable.x + (int) pWin->drawable.width +
+             wBorderWidth(pWin)) &&
+            (y >= pWin->drawable.y - wBorderWidth(pWin)) &&
+            (y < pWin->drawable.y + (int) pWin->drawable.height +
+             wBorderWidth(pWin))
+            /* When a window is shaped, a further check
+             * is made to see if the point is inside
+             * borderSize
+             */
+            && (!wBoundingShape(pWin) || PointInBorderSize(pWin, x, y))
+            && (!wInputShape(pWin) ||
+                RegionContainsPoint(wInputShape(pWin),
+                                    x - pWin->drawable.x,
+                                    y - pWin->drawable.y, &box))
+#ifdef ROOTLESS
+            /* In rootless mode windows may be offscreen, even when
+             * they're in X's stack. (E.g. if the native window system
+             * implements some form of virtual desktop system).
+             */
+            && !pWin->rootlessUnhittable
+#endif
+            ) {
+            if (pSprite->spriteTraceGood >= pSprite->spriteTraceSize) {
+                pSprite->spriteTraceSize += 10;
+                pSprite->spriteTrace = realloc(pSprite->spriteTrace,
+                                               pSprite->spriteTraceSize *
+                                               sizeof(WindowPtr));
+            }
+            pSprite->spriteTrace[pSprite->spriteTraceGood++] = pWin;
+            pWin = pWin->firstChild;
+        }
+        else
+            pWin = pWin->nextSib;
+    }
+    return DeepestSpriteWin(pSprite);
+}
+
+/**
+ * Traversed from the root window to the window at the position x/y. While
+ * traversing, it sets up the traversal history in the spriteTrace array.
+ * After completing, the spriteTrace history is set in the following way:
+ *   spriteTrace[0] ... root window
+ *   spriteTrace[1] ... top level window that encloses x/y
+ *       ...
+ *   spriteTrace[spriteTraceGood - 1] ... window at x/y
+ *
+ * @returns the window at the given coordinates.
+ */
+WindowPtr
+miXYToWindow(ScreenPtr pScreen, SpritePtr pSprite, int x, int y)
+{
+    pSprite->spriteTraceGood = 1;       /* root window still there */
+    return miSpriteTrace(pSprite, x, y);
+}