/************************************************************
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
and the Massachusetts Institute of Technology, Cambridge, Massachusetts.

                        All Rights Reserved

Permission to use, copy, modify, and distribute this software and its 
documentation for any purpose and without fee is hereby granted, 
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in 
supporting documentation, and that the names of Digital or MIT not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.  

DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
SOFTWARE.

********************************************************/


/* $Header: events.c,v 1.76 87/06/24 14:48:52 swick Exp $ */

#include "X.h"
#include "misc.h"
#include "resource.h"
#define NEED←EVENTS
#define NEED←REPLIES
#include "Xproto.h"
#include "windowstr.h"
#include "inputstr.h"
#include "scrnintstr.h"
#include "cursorstr.h"

#include "dixstruct.h"
#include "opaque.h"

extern WindowRec WindowTable[];
extern int swappedClients[];
extern Bool IsParent();

extern int (* EventSwapVector[128]) ();
extern int (* ReplySwapVector[256]) ();

#define NoSuchEvent 0x80000000	/* so doesn't match NoEventMask */
#define StructureAndSubMask ( StructureNotifyMask | SubstructureNotifyMask )
#define AllButtonsMask ( \
	Button1Mask | Button2Mask | Button3Mask | Button4Mask | Button5Mask )
#define MotionMask ( \
	PointerMotionMask | PointerMotionHintMask | Button1MotionMask | \
	Button2MotionMask | Button3MotionMask | Button4MotionMask | \
	Button5MotionMask | ButtonMotionMask )
#define PropagateMask ( \
	KeyPressMask | KeyReleaseMask | ButtonPressMask | ButtonReleaseMask | \
	MotionMask )
#define AllModifiersMask ( \
	ShiftMask | LockMask | ControlMask | Mod1Mask | Mod2Mask | \
	Mod3Mask | Mod4Mask | Mod5Mask )
#define Motion←Filter(state) (PointerMotionMask | \
		(AllButtonsMask & state) | buttonMotionMask);


#define WID(w) ((w) ? ((w)->wid) : 0)

#define BitOn(ptr, bit) \
	((BYTE *) (ptr))[(bit)>>3] |= (1 << ((bit) & 7))
#define BitOff(ptr, bit) \
	((BYTE *) (ptr))[(bit)>>3] &= ~(1 << ((bit) & 7))
#define IsOn(ptr, bit) \
	(((BYTE *) (ptr))[(bit)>>3] & (1 << ((bit) & 7)))

debug←events = 0;
InputInfo inputInfo;

KeySymsRec curKeySyms;

GrabRec keybdGrab;	/* used for active grabs */
GrabRec ptrGrab;

#define MAX←QUEUED←EVENTS 100
struct {
    unsigned int	num;
    QdEventRec		pending, free;	/* only forw, back used */
    DeviceIntPtr	replayDev;	/* kludgy rock to put flag for */
    WindowPtr		replayWin;	/*   ComputeFreezes            */
    Bool		playingEvents;
} syncEvents;

/*
 * The window trace information is used to avoid having to compute all the
 * windows between the root and the current pointer window each time a button
 * or key goes down. The grabs on each of those windows must be checked.
 */
WindowPtr *spriteTrace = (WindowPtr *)NULL;
#define ROOT spriteTrace[0]
int spriteTraceSize = 0;
int spriteTraceGood;

WindowPtr *focusTrace = (WindowPtr *)NULL;
int focusTraceSize = 0;
int focusTraceGood;

CARD16 keyButtonState = 0;
int buttonsDown = 0;		/* number of buttons currently down */
Mask buttonMotionMask = 0;

typedef struct {
    int		x, y;
} HotSpot;

struct {
    CursorPtr	current;
    BoxRec	hotLimits;	/* logical constraints */
    BoxRec	physLimits;	/* of hot spot due to hardware limits */
    WindowPtr	win;
    HotSpot	hot;
} sprite;			/* info about the cursor sprite */

Bool lastWasMotion;

extern void DoEnterLeaveEvents();	/* merely forward declarations */
extern WindowPtr XYToWindow();
extern Bool CheckKeyboardGrabs();
extern void NormalKeyboardEvent();
extern int DeliverDeviceEvents();

ScreenPtr currentScreen;

CARD16 stateMasks[MAP←LENGTH];	/* only for default keyboard ? XXX */

int lastEventMask;

#define CantBeFiltered NoEventMask
int filters[128] =
{
	NoSuchEvent,		       /* 0 */
	NoSuchEvent,		       /* 1 */
	KeyPressMask,		       /* KeyPress */
	KeyReleaseMask,		       /* KeyRelease */
	ButtonPressMask,	       /* ButtonPress */
	ButtonReleaseMask,	       /* ButtonRelease */
	MotionMask,		       /* MotionNotify - special cased */
	EnterWindowMask,	       /* EnterNotify */
	LeaveWindowMask,	       /* LeaveNotify */
	FocusChangeMask,	       /* FocusIn */
	FocusChangeMask,	       /* FocusOut */
	KeymapStateMask,	       /* KeymapNotify */
	ExposureMask,		       /* Expose */
	CantBeFiltered,		       /* GraphicsExpose */
	CantBeFiltered,		       /* NoExpose */
	VisibilityChangeMask,	       /* VisibilityNotify */
	SubstructureNotifyMask,	       /* CreateNotify */
	StructureAndSubMask,	       /* DestroyNotify */
	StructureAndSubMask,	       /* UnmapNotify */
	StructureAndSubMask,	       /* MapNotify */
	SubstructureRedirectMask,      /* MapRequest */
	SubstructureNotifyMask,	       /* ReparentNotify */
	StructureAndSubMask,	       /* ConfigureNotify */
	SubstructureRedirectMask,      /* ConfigureRequest */
	StructureAndSubMask,	       /* GravityNotify */
	ResizeRedirectMask,	       /* ResizeRequest */
	StructureAndSubMask,	       /* CirculateNotify */
	SubstructureRedirectMask,      /* CirculateRequest */
	PropertyChangeMask,	       /* PropertyNotify */
	CantBeFiltered,		       /* SelectionClear */
	CantBeFiltered,		       /* SelectionRequest */
	CantBeFiltered,		       /* SelectionNotify */
	ColormapChangeMask,	       /* ColormapNotify */
	CantBeFiltered		       /* InterpretNotify */
};

Mask
GetNextEventMask()
{
    lastEventMask <<= 1;
    return lastEventMask;
}

void
SetMaskForEvent(mask, event)
    Mask mask;
    int event;
{
    if ((event < LASTEvent) || (event >= 128))
	FatalError("MaskForEvent: bogus event number");
    filters[event] = mask;
}

static void
CheckPhysLimits(cursor)
    CursorPtr cursor;
{
    HotSpot old;

    if (!cursor)
	return;
    old = sprite.hot;
    (*currentScreen->CursorLimits) (
	currentScreen, cursor, &sprite.hotLimits, &sprite.physLimits);
/*
 * Notice that the following adjustments leave the hot spot not really where
 * it would be if you looked at the screen. This is probably the right thing
 * to do since the user does not want the hot spot to move just because the
 * hardware cannot display the physical sprite where we would like it. The
 * next time the pointer device moves, the hot spot will then "jump" to its
 * visual position.
 */
    if (sprite.hot.x < sprite.physLimits.x1)
	sprite.hot.x = sprite.physLimits.x1;
    else
	if (sprite.hot.x >= sprite.physLimits.x2)
	    sprite.hot.x = sprite.physLimits.x2 - 1;
    if (sprite.hot.y < sprite.physLimits.y1)
	sprite.hot.y = sprite.physLimits.y1;
    else
	if (sprite.hot.y >= sprite.physLimits.y2)
	    sprite.hot.y = sprite.physLimits.y2 - 1;
    if ((old.x != sprite.hot.x) || (old.y != sprite.hot.y))
	(*currentScreen->SetCursorPosition) (
	    currentScreen, sprite.hot.x, sprite.hot.y);
}

static void
NewCursorConfines(x1, x2, y1, y2)
    int x1, x2, y1, y2;
{
    sprite.hotLimits.x1 = x1;
    sprite.hotLimits.x2 = x2;
    sprite.hotLimits.y1 = y1;
    sprite.hotLimits.y2 = y2;
    CheckPhysLimits(sprite.current);
    (* currentScreen->ConstrainCursor)(currentScreen, &sprite.physLimits);
}

void
ChangeToCursor(cursor)
    CursorPtr cursor;
{
    if (!cursor)
	FatalError("Somebody is setting NullCursor");
    if (cursor != sprite.current)
    {
	if ((sprite.current->xhot != cursor->xhot) ||
		(sprite.current->yhot != cursor->yhot))
	    CheckPhysLimits(cursor);
	(*currentScreen->DisplayCursor) (
	   currentScreen, cursor, sprite.hot.x, sprite.hot.y);
	sprite.current = cursor;
    }
}

void
PostNewCursor()
{
    register    WindowPtr win;
    register    GrabPtr grab = inputInfo.pointer->grab;
    if (grab)
    {
	if (grab->u.ptr.cursor)
	{
	    ChangeToCursor(grab->u.ptr.cursor);
	    return;
	}
	if (IsParent(grab->window, sprite.win))
	    win = sprite.win;
	else
	    win = grab->window;
    }
    else
	win = sprite.win;
    for (; win; win = win->parent)
	if (win->cursor != NullCursor)
	{
	    ChangeToCursor(win->cursor);
	    return;
	}
}

/**************************************************************************
 *            The following procedures deal with synchronous events       *
 **************************************************************************/

void
EnqueueEvent(device, event)
    xEvent		*event;
    DeviceIntPtr	device;
{
    register QdEventPtr tail = syncEvents.pending.back;
    register QdEventPtr new;
/*
 * Collapsing of mouse events does not bother to test if qdEvents.num == 0,
 * since there will never be MotionNotify in the type of the head event which
 * is what last points at when num == 0.
 */
    if ((event->u.u.type == MotionNotify) && 
	(tail->event.u.u.type == MotionNotify))
    {
	tail->event = *event;
	return;
    }
    syncEvents.num++;
    if (syncEvents.free.forw == &syncEvents.free)
	new = (QdEventPtr)Xalloc(sizeof(QdEventRec));
    else
    {
	new = syncEvents.free.forw;
	remque(new);
    }
    new->device = device;
    new->event = *event;
    insque(new, tail);
    if (syncEvents.num > MAX←QUEUED←EVENTS)
    {
	/* XXX here we send all the pending events and break the locks */
	return;
    }
}

static void
PlayReleasedEvents()
{
    register QdEventPtr qe = syncEvents.pending.forw;
    QdEventPtr next;
    while (qe != &syncEvents.pending)
    {
	register DeviceIntPtr device = qe->device;
	if (!device->sync.frozen)
	{
	    next = qe->forw;;
	    remque(qe);
	    (*device->public.processInputProc)(&qe->event, device);
	    insque(qe, &syncEvents.free);
	    qe = next;
	}
	else
	    qe = qe->forw;
    } 
}

static void
ComputeFreezes(dev1, dev2)
    DeviceIntPtr dev1, dev2;
{
    register DeviceIntPtr replayDev = syncEvents.replayDev;
    int i;
    WindowPtr w;
    Bool isKbd ;
    register xEvent *xE ;

    dev1->sync.frozen =
	((dev1->sync.other != NullGrab) || (dev1->sync.state >= FROZEN));
    dev2->sync.frozen =
	((dev2->sync.other != NullGrab) || (dev2->sync.state >= FROZEN));
    if (syncEvents.playingEvents)
	return;
    syncEvents.playingEvents = TRUE;
    if (replayDev)
    {
	isKbd = (replayDev == inputInfo.keyboard);
	xE = &replayDev->sync.event;
	syncEvents.replayDev = (DeviceIntPtr)NULL;
	w = XYToWindow(
	    xE->u.keyButtonPointer.rootX, xE->u.keyButtonPointer.rootY);
	for (i = 0; i < spriteTraceGood; i++)
	    if (syncEvents.replayWin == spriteTrace[i])
	    {
		if (!CheckDeviceGrabs(replayDev, xE, i+1, isKbd))
		    if (isKbd)
			NormalKeyboardEvent(replayDev, xE, w);
		    else
			DeliverDeviceEvents(w, xE, NullGrab, NullWindow);
		goto playmore;
	    }
	/* must not still be in the same stack */
	if (isKbd)
	    NormalKeyboardEvent(replayDev, xE, w);
	else
	    DeliverDeviceEvents(w, xE, NullGrab, NullWindow);
    }
playmore:
    if (!dev1->sync.frozen || !dev2->sync.frozen)
	PlayReleasedEvents();
    syncEvents.playingEvents = FALSE;
}

CheckGrabForSyncs(grab, thisDev, thisMode, otherDev, otherMode)
    GrabPtr grab;
    DeviceIntPtr thisDev, otherDev;
    int thisMode, otherMode;
{
    if (thisMode == GrabModeSync)
	thisDev->sync.state = FROZEN←NO←EVENT;
    else
    {	/* free both if same client owns both */
	thisDev->sync.state = THAWED;
	if (thisDev->sync.other &&
	    (thisDev->sync.other->client == grab->client))
	    thisDev->sync.other = NullGrab;
    }
    if (otherMode == GrabModeSync)
	otherDev->sync.other = grab;
    else
    {	/* free both if same client owns both */
	if (otherDev->sync.other &&
	    (otherDev->sync.other->client == grab->client))
	    otherDev->sync.other = NullGrab;
	if ((otherDev->sync.state >= FROZEN) &&
	    (otherDev->grab->client == grab->client))
	    otherDev->sync.state = THAWED;
    }
    ComputeFreezes(thisDev, otherDev);
}

void
ActivatePointerGrab(mouse, grab, time, autoGrab)
    GrabPtr grab;
    register DeviceIntPtr mouse;
    TimeStamp time;
    Bool autoGrab;
{
    WindowPtr w;

    mouse->grabTime = time;
    ptrGrab = *grab;
    mouse->grab = &ptrGrab;
    mouse->u.ptr.autoReleaseGrab = autoGrab;
    CheckGrabForSyncs(
	mouse->grab, mouse, grab->pointerMode,
	inputInfo.keyboard, grab->keyboardMode);
    PostNewCursor();
    DoEnterLeaveEvents(sprite.win, grab->window, NotifyGrab);
    if (w = grab->u.ptr.confineTo)
    {
	NewCursorConfines(
	    w->absCorner.x, w->absCorner.x + w->clientWinSize.width,
	    w->absCorner.y, w->absCorner.y + w->clientWinSize.height);
    }
}

void
DeactivatePointerGrab(mouse)
    DeviceIntPtr mouse;
{
    GrabPtr grab = mouse->grab;
    DeviceIntPtr keybd = inputInfo.keyboard;

    DoEnterLeaveEvents(grab->window, sprite.win, NotifyUngrab);
    mouse->grab = NullGrab;
    mouse->sync.state = NOT←GRABBED;
    mouse->u.ptr.autoReleaseGrab = FALSE;
    if (keybd->sync.other == grab)
	keybd->sync.other = NullGrab;
    ComputeFreezes(keybd, mouse);
    if (grab->u.ptr.confineTo)
	NewCursorConfines(0, currentScreen->width, 0, currentScreen->height);
    PostNewCursor();
}

void
ActivateKeyboardGrab(keybd, grab, time, passive)
    GrabPtr grab;
    register DeviceIntPtr keybd;
    TimeStamp time;
    Bool passive;
{
    keybd->grabTime = time;
    keybdGrab = *grab;
    keybd->grab = &keybdGrab;
    keybd->u.keybd.passiveGrab = passive;
    CheckGrabForSyncs(
	keybd->grab, keybd, grab->keyboardMode,
	inputInfo.pointer, grab->pointerMode);
}

void
DeactivateKeyboardGrab(keybd)
    DeviceIntPtr keybd;
{
    DeviceIntPtr mouse = inputInfo.pointer;
    GrabPtr grab = keybd->grab;

    keybd->grab = NullGrab;
    keybd->sync.state = NOT←GRABBED;
    keybd->u.keybd.passiveGrab = FALSE;
    if (mouse->sync.other == grab)
	mouse->sync.other = NullGrab;
    ComputeFreezes(keybd, mouse);
}

static void
AllowSome(client, time, thisDev, otherDev, minFreeze)
    ClientPtr		client;
    TimeStamp		time;
    DeviceIntPtr	thisDev, otherDev;
    int			minFreeze;
{
    if (!thisDev->sync.frozen)
	return;
    if (CompareTimeStamps(time, thisDev->grabTime) == EARLIER)
	return;
    if (thisDev->sync.state < minFreeze)
	return;
    switch (minFreeze)
    {
	case NOT←GRABBED: 	       /* Async */
	    if (thisDev->grab && (thisDev->grab->client == client))
		thisDev->sync.state = THAWED;
	    if (thisDev->sync.other && (thisDev->sync.other->client == client))
		thisDev->sync.other = NullGrab;
	    ComputeFreezes(thisDev, otherDev);
	    break;
	case FROZEN←NO←EVENT:		/* Sync */
	    if (thisDev->grab->client == client)
		thisDev->sync.state = FREEZE←NEXT←EVENT;
	    ComputeFreezes(thisDev, otherDev);
	    break;
	case FROZEN←WITH←EVENT:		/* Replay */
	    if (thisDev->grab->client == client)
	    {
		syncEvents.replayDev = thisDev;
		syncEvents.replayWin = thisDev->grab->window;
		if (thisDev == inputInfo.pointer)
		    DeactivatePointerGrab(thisDev);
		else
		    DeactivateKeyboardGrab(thisDev);
		syncEvents.replayDev = (DeviceIntPtr)NULL;
	    }
	    break;
    }
}

int
ProcAllowEvents(client)
    register ClientPtr client;
{
    TimeStamp		time;
    DeviceIntPtr	mouse = inputInfo.pointer;
    DeviceIntPtr	keybd = inputInfo.keyboard;
    REQUEST(xAllowEventsReq);

    REQUEST←SIZE←MATCH(xAllowEventsReq);
    time = ClientTimeToServerTime(stuff->time);
    if (CompareTimeStamps(time, currentTime) == LATER)
	return Success;
    switch (stuff->mode)
    {
	case ReplayPointer:
	    AllowSome(client, time, mouse, keybd, FROZEN←WITH←EVENT);
	    break;
	case SyncPointer: 
	    AllowSome(client, time, mouse, keybd, FROZEN←NO←EVENT);
	    break;
	case AsyncPointer: 
	    AllowSome(client, time, mouse, keybd, NOT←GRABBED);
	    break;
	case ReplayKeyboard: 
	    AllowSome(client, time, keybd, mouse, FROZEN←WITH←EVENT);
	    break;
	case SyncKeyboard: 
	    AllowSome(client, time, keybd, mouse, FROZEN←NO←EVENT);
	    break;
	case AsyncKeyboard: 
	    AllowSome(client, time, keybd, mouse, NOT←GRABBED);
	    break;
	default: 
	    client->errorValue = stuff->mode;
	    return BadValue;
    }
    return Success;
}

void
ReleaseActiveGrabs(client)
    ClientPtr client;
{
    int i;
    register DeviceIntPtr d;
    for (i = 0; i < inputInfo.numDevices; i++)
    {
	d = inputInfo.devices[i];
	if (d->grab && (d->grab->client == client))
	{
	    if (d == inputInfo.keyboard)
		DeactivateKeyboardGrab(d);
	    else if (d == inputInfo.pointer)
		DeactivatePointerGrab(d);
	    else
		d->grab = NullGrab;
	}
    }
}

/**************************************************************************
 *            The following procedures deal with delivering events        *
 **************************************************************************/

int
TryClientEvents (client, pEvents, count, mask, filter, grab)
    ClientPtr client;
    GrabPtr grab;
    xEvent *pEvents;
    int count;
    Mask mask, filter;
{
    int i;

    if (debug←events) ErrorF(
	"Event([%d, %d], mask=0x%x), client=%d",
	pEvents->u.u.type, pEvents->u.u.detail, mask, client->index);
    if ((client) && (client != serverClient) && (!client->clientGone) &&
	((filter == CantBeFiltered) || (mask & filter)) &&
	((!grab) || (client == grab->client)))
    {
	for (i = 0; i < count; i++)
	    pEvents[i].u.u.sequenceNumber = client->sequence;
	WriteEventToClient(client, count, (pointer)pEvents);
	if (debug←events) ErrorF(  " delivered\n");
	return 1;
    }
    else
    {
	if (debug←events) ErrorF("\n");
	return 0;
    }
}

int
DeliverEventsToWindow(pWin, pEvents, count, filter, grab)
    WindowPtr pWin;
    GrabPtr grab;
    xEvent *pEvents;
    int count;
    Mask filter;
{
    int     deliveries = 0;
    OtherClients *other;
    ClientPtr client = NullClient;

/*
 * The following relies on the fact that the Button<n>MotionMasks are equal
 * to the corresponding Button<n>Masks from the current modifier/button state.
 * If the client only selected one of the Button<n>Motion events, then she
 * should only get those.
 */

    if (pEvents->u.u.type == MotionNotify)
    {
        if (pWin->allEventMasks & PointerMotionHintMask)
	{
    	    if (lastWasMotion)
                return 0;
            else 
    	        pEvents->u.u.detail = NotifyHint;
	}
        lastWasMotion = TRUE;
	filter = Motion←Filter(keyButtonState);
    }

/* if nobody ever wants to see this event, skip some work */
    if ((filter != CantBeFiltered) && !(pWin->allEventMasks & filter))
	return 0;
    if (TryClientEvents(
	pWin->client, pEvents, count, pWin->eventMask, filter, grab))
    {
	deliveries++;
	client = pWin->client;
    }
    if (filter) /* CantBeFiltered means only window owner gets the event */
	for (other = OTHERCLIENTS(pWin); other; other = other->next)
	{
	    if (TryClientEvents(
		  other->client, pEvents, count, (Mask) other->mask, filter, grab))
	    {
		deliveries++;
		client = other->client;
	    }
	}
    if ((pEvents->u.u.type == ButtonPress) && deliveries && (!grab))
    {
	ptrGrab.device = inputInfo.pointer;
	ptrGrab.client = client;
	ptrGrab.window = pWin;
	ptrGrab.ownerEvents = pWin->eventMask & OwnerGrabButtonMask;
	ptrGrab.eventMask =  pWin->eventMask;
	ptrGrab.keyboardMode = GrabModeAsync;
	ptrGrab.pointerMode = GrabModeAsync;
	ptrGrab.u.ptr.confineTo = NullWindow;
	ptrGrab.u.ptr.cursor = NullCursor;
	ActivatePointerGrab(inputInfo.pointer, &ptrGrab, currentTime, TRUE);
    }
    return deliveries;
}

/* If the event goes to dontDeliverToMe, don't send it and return 0.  if
   send works,  return 1 or if send didn't work, return 2.
*/

int
MaybeDeliverEventsToClient(pWin, pEvents, count, filter, dontDeliverToMe)
    WindowPtr pWin;
    xEvent *pEvents;
    int count;
    Mask filter;
    ClientPtr dontDeliverToMe;
{
    OtherClients * other;

    if (pWin->eventMask & filter)
    {
        if (pWin->client == dontDeliverToMe)
		return 0;
	return TryClientEvents(
	    pWin->client, pEvents, count, pWin->eventMask, filter, NullGrab);
    }
    for (other = OTHERCLIENTS(pWin); other; other = other->next)
	if (other->mask & filter)
	{
            if (other->client == dontDeliverToMe)
		return 0;
	    return TryClientEvents(
		other->client, pEvents, count, (Mask) other->mask, filter, NullGrab);
	}
    return 2;
}

WindowPtr
RootForWindow(pWin)
    WindowPtr pWin;
{
    return &WindowTable[pWin->drawable.pScreen->myNum];
}

void
FixUpEventFromWindow(xE, pWin, child, calcChild)
    xEvent *xE;
    WindowPtr pWin;
    Window child;
    Bool calcChild;
{
    if (calcChild)
    {
        WindowPtr w=spriteTrace[spriteTraceGood-1];

        while (w) 
        {
 	    if (w == pWin)
	    {
 		child = w->wid;
		break;
	    }
 	    w = w->parent;
        } 	    
    }
    xE->u.keyButtonPointer.root = ROOT->wid;
    xE->u.keyButtonPointer.child = child;
    xE->u.keyButtonPointer.event = pWin->wid;
    xE->u.keyButtonPointer.eventX =
	xE->u.keyButtonPointer.rootX - pWin->absCorner.x;
    xE->u.keyButtonPointer.eventY =
	xE->u.keyButtonPointer.rootY - pWin->absCorner.y;
}


int
DeliverDeviceEvents(pWin, xE, grab, stopAt)
    register WindowPtr pWin, stopAt;
    register xEvent *xE;
    GrabPtr grab;
{
    Mask filter;
    int     deliveries;
    Window child = None;

    filter = filters[xE->u.u.type];
    if ((filter != CantBeFiltered) && !(filter & pWin->deliverableEvents))
	return 0;
    while (pWin)
    {
	FixUpEventFromWindow(xE, pWin, child, FALSE);
	deliveries = DeliverEventsToWindow(pWin, xE, 1, filter, grab);
	if ((deliveries > 0) || (filter & pWin->dontPropagateMask))
	    return deliveries;
	if (pWin == stopAt)
	    return 0;
	child = pWin->wid;
	pWin = pWin->parent;
    }
/*
 * This point should never be reached. Either stopAt is NullWindow, in which
 * case, the procedure is exited from the middle of the loop above, or it is
 * a window that the caller is asserting is an ancestor of pWin.
 */
    return 0;
}

int
DeliverEvents(pWin, xE, count, otherParent)
/* not useful for events that propagate up the tree */
    register WindowPtr pWin, otherParent;
    register xEvent *xE;
    int count;
{
    Mask filter;
    int     deliveries;

    if (!count)
	return 0;
    filter = filters[xE->u.u.type];
    if ((filter & SubstructureNotifyMask) && (xE->u.u.type != CreateNotify))
	xE->u.destroyNotify.event = pWin->wid;
    if (filter != StructureAndSubMask)
	return DeliverEventsToWindow(pWin, xE, count, filter, NullGrab);
    deliveries = DeliverEventsToWindow(
	    pWin, xE, count, StructureNotifyMask, NullGrab);
    if (pWin->parent)
    {
	xE->u.destroyNotify.event = pWin->parent->wid;
	deliveries += DeliverEventsToWindow(
		pWin->parent, xE, count, SubstructureNotifyMask, NullGrab);
	if (xE->u.u.type == ReparentNotify)
	{
	    xE->u.destroyNotify.event = otherParent->wid;
	    deliveries += DeliverEventsToWindow(
		    otherParent, xE, count, SubstructureNotifyMask, NullGrab);
	}
    }
    return deliveries;
}

/* check root -- this fails in Zaphod mode XXX */
/* 
 * XYToWindow is only called by CheckMotion after it has determined that
 * the current cache is not accurate.
 */
static WindowPtr 
XYToWindow(x, y)
	int x, y;
{
    register WindowPtr  pWin;

    spriteTraceGood = 1;	/* root window still there */
    pWin = ROOT->firstChild;
    while (pWin)
    {
	if ((pWin->mapped) &&
		(x >= pWin->absCorner.x - pWin->borderWidth) &&
		(x < pWin->absCorner.x + pWin->clientWinSize.width +
		    pWin->borderWidth) &&
		(y >= pWin->absCorner.y - pWin->borderWidth) &&
		(y < pWin->absCorner.y + pWin->clientWinSize.height +
		    pWin->borderWidth))
	{
	    if (spriteTraceGood >= spriteTraceSize)
	    {
		spriteTraceSize += 10;
		spriteTrace = (WindowPtr *)Xrealloc(
		    spriteTrace, spriteTraceSize*sizeof(WindowPtr));
	    }
	    spriteTrace[spriteTraceGood] = pWin;
	    pWin = spriteTrace[spriteTraceGood++]->firstChild;
	}
	else
	    pWin = pWin->nextSib;
    }
    return spriteTrace[spriteTraceGood-1];
}

WindowPtr 
CheckMotion(x, y, ignoreCache)
    int x, y;
    Bool ignoreCache;
{
    WindowPtr prevSpriteWin = sprite.win;

    if ((x != sprite.hot.x) || (y != sprite.hot.y))
    {
	sprite.win = XYToWindow(x, y);
	sprite.hot.x = x;
	sprite.hot.y = y;
/* XXX Do PointerNonInterestBox here */
/*
	if (!(sprite.win->deliverableEvents & Motion←Filter(keyButtonState)))
        {
	    
	}
*/
    }
    else
    {
	if ((ignoreCache) || (!sprite.win))
	    sprite.win = XYToWindow(x, y);
    }
    if (sprite.win != prevSpriteWin)
    {
	if (prevSpriteWin != NullWindow)
	    DoEnterLeaveEvents(prevSpriteWin, sprite.win, NotifyNormal);
	lastWasMotion = FALSE;
	PostNewCursor();
        return NullWindow;
    }
    return sprite.win;
}

WindowsRestructured()
{
    CheckMotion((int)sprite.hot.x, (int)sprite.hot.y, (Bool)TRUE);
}

void
DefineInitialRootWindow(win)
    WindowPtr win;
{
    register CursorPtr c = win->cursor;

    sprite.hot.x = currentScreen->width / 2;
    sprite.hot.y = currentScreen->height / 2;
    sprite.win = win;
    sprite.current = c;
    ROOT = win;
    (*currentScreen->CursorLimits) (
	currentScreen, win->cursor, &sprite.hotLimits, &sprite.physLimits);
    (*currentScreen->SetCursorPosition) (
	currentScreen, sprite.hot.x, sprite.hot.y);
    (*currentScreen->ConstrainCursor) (
	currentScreen, &sprite.physLimits);
    (*currentScreen->DisplayCursor) (
	currentScreen, c, sprite.hot.x, sprite.hot.y);
}

/*
 * This does not take any shortcuts, and even ignores its argument, since
 * it does not happen very often, and one has to walk up the tree since
 * this might be a newly instantiated cursor for an intermediate window
 * between the one the pointer is in and the one that the last cursor was
 * instantiated from.
 */
void
WindowHasNewCursor(pWin)
    WindowPtr pWin;
{
    PostNewCursor();
}

void
NewCurrentScreen(newScreen, x, y)
    ScreenPtr newScreen;
    int x,y;
{
    if (newScreen == currentScreen)
        return;
    ROOT = &WindowTable[newScreen->myNum];
    (void) CheckMotion(x, y, TRUE);
}

ProcWarpPointer(client)
    ClientPtr client;
{
    WindowPtr  source, dest;
    REQUEST(xWarpPointerReq);

    REQUEST←SIZE←MATCH(xWarpPointerReq);
    dest = (WindowPtr) LookupID(stuff->dstWid, RT←WINDOW, RC←CORE);
    if (!dest)
    {
	client->errorValue = stuff->dstWid;
	return BadWindow;
    }
    if (stuff->srcWid != None)
    {
	int     winX, winY;
	source = (WindowPtr ) LookupID(stuff->srcWid, RT←WINDOW, RC←CORE);
	if (!source)
	{
	    client->errorValue = stuff->srcWid;
	    return BadWindow;
	}
	winX = source->absCorner.x;
	winY = source->absCorner.y;
	if (
		(sprite.hot.x < (winX + stuff->srcX)) ||
		(sprite.hot.y < (winY + stuff->srcY)) ||
		((stuff->srcWidth != 0) &&
		    (winX + stuff->srcX + stuff->srcWidth < sprite.hot.x)) ||
		((stuff->srcHeight != 0) &&
		    (winY + stuff->srcY + stuff->srcHeight < sprite.hot.y)) ||
		(!PointInWindowIsVisible(source, sprite.hot.x, sprite.hot.y)))
	    return Success;
    }
    if (currentScreen != dest->drawable.pScreen)
        NewCurrentScreen(dest->drawable.pScreen, 
	    	         dest->absCorner.x + stuff->dstX,
		         dest->absCorner.y + stuff->dstY);
    (*dest->drawable.pScreen->SetCursorPosition)( dest->drawable.pScreen,
	    dest->absCorner.x + stuff->dstX, dest->absCorner.y + stuff->dstY);
    return Success;
}

static Bool
IsGrabbed(key, modifiers, dev, grab, keybd)
    int key, modifiers;
    DeviceIntPtr dev;
    register GrabPtr grab;
    Bool keybd;
{
    if (grab->device != dev)
	return FALSE;
    if ((grab->modifiers != AnyModifier) && (grab->modifiers != modifiers))
	return FALSE;
    if (keybd)
    {
	if ((key != grab->u.keybd.key) &&
	    ((grab->u.keybd.key != AnyKey) || (stateMasks[key])))
	    return FALSE;
    }
    else
    {
	if ((key != grab->u.ptr.button) && (grab->u.ptr.button != AnyButton))
	    return FALSE;
    }
    return TRUE;
}

Bool
MatchingGrab(key, modifiers, dev, grab, keybd)
    int key, modifiers;
    DeviceIntPtr dev;
    register GrabPtr grab;
    Bool keybd;
{
    if (grab->device != dev)
	return FALSE;
    if ((grab->modifiers != modifiers) &&
	(grab->modifiers != AnyModifier) &&
	(modifiers != AnyModifier))
	return FALSE;
    if (keybd)
    {
	if ((key != grab->u.keybd.key) &&
	    ((grab->u.keybd.key != AnyKey) || (stateMasks[key])) &&
	    ((key != AnyKey) || (stateMasks[grab->u.keybd.key])))
	    return FALSE;
    }
    else
    {
	if ((key != grab->u.ptr.button) &&
	    (grab->u.ptr.button != AnyButton) &&
	    (key != AnyButton))
	    return FALSE;
    }
    return TRUE;
}

void
NoticeTimeAndState(xE)
    register xEvent *xE;
{
    if (xE->u.keyButtonPointer.time < currentTime.milliseconds)
	currentTime.months++;
    currentTime.milliseconds = xE->u.keyButtonPointer.time;
    xE->u.keyButtonPointer.pad1 = 0;
    xE->u.keyButtonPointer.state = keyButtonState;
    xE->u.keyButtonPointer.sameScreen = TRUE;		/* XXX */
}

Bool
CheckDeviceGrabs(device, xE, checkFirst, isKeyboard)
    register DeviceIntPtr device;
    register xEvent *xE;
    int checkFirst;
{
    int i;
    GrabPtr grab;
    Bool sawFocus = (focusTraceGood == 1);
    WindowPtr pWin;
    for (i = checkFirst; i < spriteTraceGood; i++)
    {
	pWin = spriteTrace[i];
        if (isKeyboard && !sawFocus)
	{
            if ((focusTraceGood > i) || (focusTrace[i] != pWin))
                return FALSE;
            if (pWin == inputInfo.keyboard->u.keybd.focus.win)
                sawFocus == TRUE;
        }
	for (grab = PASSIVEGRABS(pWin); grab; grab = grab->next)
	{
	    if (IsGrabbed(
		    (int)xE->u.u.detail, (int)keyButtonState & AllModifiersMask,
		    device, grab, isKeyboard))
	    {
		if (isKeyboard)
		    ActivateKeyboardGrab(device, grab, currentTime, TRUE);
		else
		    ActivatePointerGrab(device, grab, currentTime, TRUE);
 
		FixUpEventFromWindow(xE, grab->window, None, TRUE);
		TryClientEvents(
		     grab->client, xE, 1, grab->eventMask, 
				(Mask)filters[xE->u.u.type],  grab);
		if (device->sync.state == FROZEN←NO←EVENT)
		{
		    device->sync.event = *xE;
		    device->sync.state = FROZEN←WITH←EVENT;
		}
		return TRUE;
	    }
	}
    }
    return FALSE;
}

static void
NormalKeyboardEvent(keybd, xE, window)
    xEvent *xE;
    DeviceIntPtr keybd;
    WindowPtr window;
{
    WindowPtr focus = keybd->u.keybd.focus.win;
    if (focus == NullWindow)
	return;
    if (focus == PointerRootWin)
    {
	DeliverDeviceEvents(window, xE, NullGrab, NullWindow);
	return;
    }
    if ((focus == window) || IsParent(focus, window))
    {
	if (DeliverDeviceEvents(window, xE, NullGrab, focus))
	    return;
    }
 /* just deliver it to the focus window */
    FixUpEventFromWindow(xE, focus, None, FALSE);
    DeliverEventsToWindow(focus, xE, 1, (Mask)filters[xE->u.u.type], NullGrab);
}

void
ProcessKeyboardEvent (xE, keybd)
    register xEvent *xE;
    register DeviceIntPtr keybd;
{
    register int    key;
    GrabPtr         grab = keybd->grab;
    WindowPtr       pWin;
    Bool            deactiveGrab = FALSE;

    if (keybd->sync.frozen)
    {
	EnqueueEvent(keybd, xE);
	return;
    }
    NoticeTimeAndState(xE);
    key = xE->u.u.detail;
    pWin = sprite.win;
/*
    CheckMotion(
	xE->u.keyButtonPointer.rootX, xE->u.keyButtonPointer.rootY,
	FALSE);
    xE->u.keyButtonPointer.rootX = sprite.hot.x;  ignore x and y for keyboard?
    xE->u.keyButtonPointer.rootY = sprite.hot.y;
*/
    xE->u.u.detail = key;           
    lastWasMotion  = FALSE;
    switch (xE->u.u.type)
    {
	case KeyPress: 
	    BitOn(keybd->down, key);
	    if (!xE->u.u.detail)
		return;
	    BitOn(keybd->down, xE->u.u.detail);
	    keyButtonState |= stateMasks[xE->u.u.detail];
	    if (!grab)
		if (CheckDeviceGrabs(keybd, xE, 0, TRUE))
		    return;
	    break;
	case KeyRelease: 
	    BitOff(keybd->down, key);
	    if (!xE->u.u.detail)
		return;
	    BitOff(keybd->down, xE->u.u.detail);
	    keyButtonState &= ~stateMasks[xE->u.u.detail];
	    if ((keybd->u.keybd.passiveGrab) &&
			(xE->u.u.detail == grab->u.keybd.key))
		deactiveGrab = TRUE;
	    break;
	default: 
	    FatalError("Impossible keyboard event");
    }
    if (grab = keybd->grab)
    {
	Bool syncIt;
	if ((!grab->ownerEvents) ||
		(!(syncIt = DeliverDeviceEvents(pWin, xE, grab, NullWindow))))
	{
	    FixUpEventFromWindow(xE, grab->window, None, TRUE);
	    syncIt = TryClientEvents(
		grab->client, xE, 1, grab->eventMask, 
		(Mask)filters[xE->u.u.type], grab);
	}
	if (syncIt && (keybd->sync.state == FREEZE←NEXT←EVENT))
	{
	    keybd->sync.state = FROZEN←WITH←EVENT;
	    keybd->sync.frozen = TRUE;
	    keybd->sync.event = *xE;
	}
    }
    else
	NormalKeyboardEvent(keybd, xE, pWin);
    if (deactiveGrab)
        DeactivateKeyboardGrab(keybd);
}