#ifndef lint
static char sccsid[] = "@(#)scene.c 9.9 88/02/10 Copyright 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc.
 */

/*-
	Routines for dealing with sets of canvases (==scenes)

	Most of the algorithms for manipulating the
	canvas hierarchy are here.  Beware!

	scene.c, Wed Oct 16 18:11:02 1985

 */

#include <stdio.h>
#ifdef REF
#include <sys/types.h>
#include <ref/config.h>
#endif
#include "shape.h"
#include "canvas.h"
#include "cursor.h"
#include "qalloc.h"

static      InvalidationGeneration, GenerationDepth;
static      subgeneration;
extern struct pixrect *mem_create();
extern struct pixrectops cv_ops;

/* Save the fragment of canvas p under shape i */
cv_save_fragment(p, i)
    register struct canvas *p;
    register struct shape *i;
{
    assert(p != 0 && i != 0);
    if (!p->complete && p->retained) {
	if (!p->validpix)
	    cv_validate_pixrects(p);
	pr_shaperop(p->retained_part.pixrect, i, PIX_SRC,
		    p->screen_part.pixrect, 0, 0);
    }
}

/* Restore the fragment of canvas p under shape i */
cv_restore_fragment(p, i)
    register struct canvas *p;
    register struct shape *i;
{
    assert(p != 0 && i != 0);
    if (subgeneration > p->invgeneration) {
	if (p->retained) {
	    if (!p->validpix)
		cv_validate_pixrects(p);
	    pr_shaperop(p->screen_part.pixrect, i, PIX_SRC,
			p->retained_part.pixrect, 0, 0);
	}
	else
	    cv_extend_damage(p, i);
    }
}

/*
 * Iterate through all the opaque children (and opaque children of transparent
 * children) of canvas cv, subtract their outlines from shape sh, offsetting
 * these outlines by (offx,offy) and intersecting them with the boundary.  Sh,
 * with the opaque children of cv subtracted, is returned. It calls itself
 * recursivly to deal with the opaque children of transparent children, which
 * are the only calls that should be using non-zero values of offx, offy and
 * boundary
 */
struct shape *
cv_subtract_opaque_children(cv, sh, offx, offy, boundary)
    register struct canvas *cv;
    register struct shape *sh;
{
    if (cv == 0 || !cv->hasopaque || cv->outerclip == 0)
	return sh;
    for (cv = cv->topchild; cv && sh; cv = cv->prev)
	if (cv->mapped)
	    if (cv->transparent) {
		if (cv->hasopaque) {
		    register struct shape *tsh = cv->outerclip;
		    sh_incref(tsh);
		    tsh = sh_translate(tsh, offx + cv->pos.x,
				       offy + cv->pos.y);
		    if (boundary) {
			register struct shape *tsh2 =
			sh_intersect(tsh, boundary);
			sh_decref(tsh);
			tsh = tsh2;
		    }
		    if (tsh) {
			sh = cv_subtract_opaque_children(cv, sh,
				    offx + cv->pos.x, offx + cv->pos.y, tsh);
			sh_decref(tsh);
		    }
		}
	    }
	    else {
		register struct shape *tsh,
		           *tsh2;
		tsh = cv->outerclip;
		sh_incref(tsh);
		tsh = sh_translate(tsh, offx + cv->pos.x, offy + cv->pos.y);
		if (boundary) {
		    tsh2 = sh_intersect(boundary, tsh);
		    sh_decref(tsh);
		    tsh = tsh2;
		}
		if (tsh) {
		    tsh2 = sh_difference(sh, tsh);
		    sh_decref(sh);
		    sh_decref(tsh);
		    sh = tsh2;
		}
	    }
    return sh;
}

/*
 * Compute the shape of the visible part of canvas cv, considering it's opaque
 * children if requested.  The algorithm is basically to find the visible part
 * of it's parent, intersect that with the shape of the canvas, and then
 * subtract away the shapes of its upper opaque siblings
 */
struct shape *
cv_compute_visible_part(cv, consider_opaque_children)
    register struct canvas *cv;
{
    register struct shape *ret,
               *psh;
    register struct canvas *p;
    struct spoint pos;
    if (!cv->mapped)
	return 0;
    if (cv->screen_part.pixrect == 0) {
	if (!cv->validpix)
	    cv_validate_pixrects(cv);
	if (cv->screen_part.pixrect == 0)
	    return 0;
    }
    if (cv->parent) {
	psh = sh_translate(cv_compute_visible_part(cv->parent,
						    /* cv->transparent */ 0),
			   -cv->pos.x, -cv->pos.y);
	ret = sh_intersect(cv->outerclip, psh);
	if (psh)
	    sh_decref(psh);
    }
    else {
	ret = cv->outerclip;
	sh_incref(ret);
    }
    if (cv->hasopaque && consider_opaque_children)
	ret = cv_subtract_opaque_children(cv, ret, 0, 0, 0);
    if (cv->parent && cv->parent->hasopaque && ret) {
	pos = cv->pos;		/* Consider upper siblings */
	for (p = cv->next; p; p = p->next)
	    if (p->mapped && !p->transparent && cv_overlap_possible(cv, p)) {
		ret = sh_translate(ret, pos.x - p->pos.x, pos.y - p->pos.y);
		pos = p->pos;
		if (overlap_possible(ret, p->outerclip)) {
		    register struct shape *diff;
		    diff = sh_difference(ret, p->outerclip);
		    sh_decref(ret);
		    if (diff == 0)
			return 0;
		    ret = diff;
		}
	    }
	ret = sh_translate(ret, pos.x - cv->pos.x, pos.y - cv->pos.y);
    }
    if (ret)
	trim_traps(ret);
/*- else if (cv->retained)
	cv->complete = 1; */
    return ret;
}

static
nop() {}

static struct pixrect *
nop_region() { return 0; }

extern cv_destroy();

static
struct pixrectops nulldev_ops = {
    nop,
    nop,
    nop,
    nop,
    cv_destroy,
    nop,
    nop,
    nop,
    nop_region,
    nop,
    nop,
    nop,
    nop,
    nop,
    nop,
    nop,
    nop,
    nop,
};

/*
 * Returns true if canvas p is being clipped to the rectangle that corresponds
 * exactly to its underlying pixrect
 */
#define UsesWholePixrect(p) \
       (p.clip && p.pixrect && p.clip->is_rect \
	&& p.clip->pos.x == 0 && p.clip->pos.y == 0 \
	&& p.clip->size.x == p.pixrect->pr_width \
	&& p.clip->size.y == p.pixrect->pr_height \
	&& cv->pixrect.pr_width == p.pixrect->pr_width \
	&& cv->pixrect.pr_height == p.pixrect->pr_height)

/*
 * Validates the clip cache information for canvas "cv", with respect to the
 * clipping outline "clip".  Conceptually, graphics operations on a canvas are
 * clipped to the intersection of the per-process clip, the per-canvas clip
 * and the shape of the canvas.  The "clip" argument is generally the
 * per-process clip.  When a graphics operation is actually done, it is
 * actually done in two places: the screen_part and the retained_part.  Each
 * part has a shape associated with it.  Either shape may be empty.  These two
 * shapes are formed by first intersecting the three conceptual clipping
 * shapes into one shape, and then splitting that shape into two, one part is
 * visible, the other isn't.
 * 
 * The computation of these two clipping shapes is expensive, and hence cached.
 * "cv->lastclip" is the last per-process clipping boundary against which they
 * were validated.
 */
cv_validate_clip(cv, clip)
    register struct canvas *cv;
    register struct shape *clip;
{
    register struct shape *cl,
               *realclip;
    register struct pixrect *pix;

    assert(clip != 0);
    if (cv->lastclip == clip)
	return;
    if (!cv->validpix)
	cv_validate_pixrects(cv);
    if (cv->overlay) {
	if (cv->lastclip && cv->lastclip->refcnt != STATIC_OBJ)
	    sh_decref(cv->lastclip);
	if (cv->lastclip = clip)
	    sh_incref(cv->lastclip);
	return;
    }
    cv->invgeneration = 0;
    cv->opaqparent->invgeneration = 0;
    if (cv->screen_part.clip)
	sh_decref(cv->screen_part.clip);
    if (cv->retained_part.clip)
	sh_decref(cv->retained_part.clip);
    cl = cv_compute_visible_part(cv, 1);
    if (cv->opaqparent->globalclip) {
	register struct canvas *tcv;
	register struct shape *tsh;
	register    dx = 0,
	            dy = 0;
	for (tcv = cv; tcv && tcv != cv->opaqparent; tcv = tcv->parent) {
	    dx += tcv->pos.x;
	    dy += tcv->pos.y;
	}
	tsh = cv->opaqparent->globalclip;
	sh_incref(tsh);
	tsh = sh_translate(tsh, -dx, -dy);
	realclip = sh_intersect(tsh, clip);
	if (tsh)
	    sh_decref(tsh);
	trim_traps(realclip);
    }
    else {
	realclip = clip;
	sh_incref(realclip);
    }
    if (cv->screen_part.pixrect)
	cv->screen_part.clip = sh_intersect(realclip, cl);
    else
	cv->screen_part.clip = 0;
    if (cv->retained && cv->retained_part.pixrect && realclip)
	if (cv->screen_part.pixrect)
	    cv->retained_part.clip = sh_difference(realclip, cl);
	else {
	    cv->retained_part.clip = realclip;
	    sh_incref(realclip);
	}
    else
	cv->retained_part.clip = 0;
    if (realclip)
	sh_decref(realclip);
    if (cl)
	sh_decref(cl);
    if (UsesWholePixrect(cv->screen_part)) {
	register struct canvas *opsmash;
	cv->pixrect.pr_ops = cv->screen_part.pixrect->pr_ops;
	cv->pixrect.pr_data = cv->screen_part.pixrect->pr_data;
	for (opsmash = cv->opaqparent; opsmash; opsmash = opsmash->parent)
	    opsmash->complete = 0;
    }
    else if (cv->retained && UsesWholePixrect(cv->retained_part)) {
	cv->pixrect.pr_ops = cv->retained_part.pixrect->pr_ops;
	cv->pixrect.pr_data = cv->retained_part.pixrect->pr_data;
/*XX	cv->opaqparent->complete = 1; */
    }
    else
	cv->pixrect.pr_ops = &cv_ops;
    if (cv->screen_part.clip == 0) {
	if (cv->retained_part.clip == 0)
	    cv->pixrect.pr_ops = &nulldev_ops;
/*-	if (cv->retained)
	    cv->complete = 1; */
    }
    if (cv->lastclip && cv->lastclip->refcnt != STATIC_OBJ)
	sh_decref(cv->lastclip);
    sh_incref(clip);
    cv->lastclip = clip;
}

/* Return the mapped, opaque canvas visually below cv */
struct canvas *
cv_below(cv)
    register struct canvas *cv;
{
    while (1) {
	if (cv->prev) {
	    cv = cv->prev;
	    while (cv->topchild && cv->mapped && !cv->transparent)
		cv = cv->topchild;
	}
	else if (cv->parent)
	    cv = cv->parent;
	else
	    return 0;
	if (cv->mapped && !cv->transparent)
	    return cv;
    }
}



/* remove a canvas from its scene */
cs_remove(cv, savebits)
    register struct canvas *cv;
{
    register struct canvas *p;
    if (cv->parent == 0)
	return;
    cv_unmap(cv, savebits);
    cv_invalidate_clip(cv, 1);
    cv_invalidate_pixrects(cv);
    p = cv->prev;
    if (cv->next) {
	assert(p == 0 || cv->next != p);
	cv->next->prev = p;
    }
    else if (cv->parent->topchild == cv) {
	assert(p == 0 || p->parent == cv->parent);
	cv->parent->topchild = p;
    }
    if (p)
	p->next = cv->next;
    cv->next = 0;
    cv->prev = 0;
    cv_decref(cv->parent);
    cv->parent = 0;
}

cs_setparent(cv, newpar)
    register struct canvas *cv, *newpar;
{
    register struct canvas *p;
    if (cv->parent == newpar)
	return 0;
    for (p = newpar; p; p = p->parent)
	if (p == cv) return -1;
    cs_remove(cv, 1);
    cv->parent = newpar;
    cv_incref(newpar);
    if (cv->prev = newpar->topchild)
	cv->prev->next = cv;
    newpar->topchild = cv;
    if (cv->map_req)
	cv_map(cv, 1);
    return 0;
}

/* Mark the region of canvas "cv" described by shape "sh" as damaged */
cv_extend_damage(cv, sh)
    register struct canvas *cv;
    register struct shape *sh;
{
    register struct shape *tsh;
    if (cv == 0 || sh == 0)
	return;
    tsh = sh;
    sh_incref(tsh);
    while (cv != cv->opaqparent) {
	tsh = sh_translate(tsh, cv->pos.x, cv->pos.y);
	assert(cv->parent && cv->opaqparent == cv->parent->opaqparent);
	cv = cv->parent;
    }
    if (cv->damage == 0) {
	cv->damage = tsh;
	if (!cv->indamqueue) {
	    cv->damnext = cv_damage_list;
	    cv->indamqueue = 1;
	    cv_damage_list = cv;
	}
    }
    else {
	register struct shape *dsh = cv->damage;
	register int T;
	if (!dsh->is_rect || dsh->refcnt > 1) {
	    qtalloc(dsh, (struct shape *));
	    *dsh = *cv->damage;
	    dsh->refcnt = 1;
	    dsh->is_rect = 1;
	    dsh->trapset = 0;
	    sh_decref(cv->damage);
	    cv->damage = dsh;
	}
	if ((T = tsh->pos.x - dsh->pos.x) < 0) {
	    dsh->pos.x = tsh->pos.x;
	    dsh->size.x -= T;
	}
	if ((T = tsh->pos.x + tsh->size.x - dsh->pos.x - dsh->size.x) > 0)
	    dsh->size.x += T;
	if ((T = tsh->pos.y - dsh->pos.y) < 0) {
	    dsh->pos.y = tsh->pos.y;
	    dsh->size.y -= T;
	}
	if ((T = tsh->pos.y + tsh->size.y - dsh->pos.y - dsh->size.y) > 0)
	    dsh->size.y += T;
	sh_decref(tsh);
    }
}

cv_DO_extenddamage(gc, mask)
    register struct graphics_context *gc;
{
    register struct shape *outline;
    outline = cv_pathtoshape(gc, mask);
    if (outline) {
	cv_extend_damage(gc->canvas, outline);
	sh_decref(outline);
    }
    cs_newpath(gc);
}


/* unmap a canvas from its scene */
cv_unmap(cv, savebits)
    register struct canvas *cv;
{
    register struct shape *vp;
    struct spoint pos;
    register struct canvas *p;
    if (!cv->mapped || cv->parent == 0)
	return;
    cv->invgeneration = 0;
    cv->opaqparent->invgeneration = 0;
    for (p = cv->topchild; p; p = p->prev)
	cv_unmap(p, 1);
    if (!cv->transparent) {
	subgeneration = 99;
	vp = cv_compute_visible_part(cv, 0);
	cs_checkcursorcanvas(cv);
	if (cv->retained) {
	    if (!cv->complete && vp && vp->size.x > 0 && savebits)
		pr_shaperop(cv->retained_part.pixrect, vp, PIX_SRC,
			    cv->screen_part.pixrect, 0, 0);
	    cv->complete = 1;
	}
	if (cv->saveback && cv->retained_part.pixrect) {
	    {
		register struct canvas *upper = cv->next;
		while (upper && !upper->mapped)
		    upper = upper->next;
		if (upper == 0) {
		    pr_shaperop(cv->screen_part.pixrect, vp, PIX_SRC,
				cv->retained_part.pixrect, 0, 0);
		    subgeneration = cv->subgeneration;
		}
	    }
	    pr_destroy(cv->retained_part.pixrect);
	    cv->retained_part.pixrect = 0;
	    if (cv->subgeneration <= GenerationDepth) {
		GenerationDepth = cv->subgeneration - 1;
		if (GenerationDepth <= 1)
		    GenerationDepth = 0;
	    }
	    InvalidationGeneration = GenerationDepth;
	}
	p = cv;
	pos = cv->pos;
	cv->mapped = 0;
	cv_apply_to_intersecting_fragments_of_parent(cv->pos, vp, cv->parent,
						     0, cv_restore_fragment);
	InvalidationGeneration = 0;
	if (vp)
	    sh_decref(vp);
	subgeneration = 99;
    }
    cv_invalidate_pixrects(cv);
    cv_invalidate_clip(cv, 1);
    cv->mapped = 0;
}


/* insert a canvas into its scene */
cv_insert(cv, after, savebits)
    register struct canvas *cv,
               *after;
{
    struct canvas *oldparent;
    if (cv->overlay)
	return;
    assert(cv != after && cv && after);
    if (oldparent = cv->parent) {
	cv_incref(oldparent);	/* cs_remove does a decref */
	cs_remove(cv, savebits);
	cv->parent = oldparent;
    }
    {
	register struct canvas *p;
	for (p = cv->topchild; p; p = p->prev)
	    cv_unmap(p, 1);
    }
    if (after == cv->parent) {
	if (after->topchild == 0) {
	    after->topchild = cv;
	    cv->next = 0;
	}
	else {
	    for (after = after->topchild; after->prev; after = after->prev);
	    assert(after != cv);
	    after->prev = cv;
	    cv->next = after;
	}
	cv->prev = 0;
    }
    else {
	assert(cv->parent == after->parent);
	cv->prev = after;
	if (cv->next = after->next) {
	    assert(after->next != cv);
	    after->next->prev = cv;
	}
	else
	    cv->parent->topchild = cv;
	after->next = cv;
    }
    cv->scene = after->scene;
    if (cv->map_req)
	cv_map(cv, savebits);
    else {
	cv_invalidate_clip(cv, 1);
	cv_invalidate_pixrects(cv);
    }
}

/*
 * The calculation of the screen_part and retained_part pixrects of a canvas
 * is also cached.  This routine invalidates the cache & throws away the
 * pixrects. Normally, these pixrects are regions of the parents corresponding
 * pixrects
 */
cv_invalidate_pixrects(cv)
    register struct canvas *cv;
{
    register struct canvas *child;
    if (cv == 0 || !cv->validpix || cv->parent == 0)
	return;
    for (child = cv->topchild; child; child = child->prev)
	cv_invalidate_pixrects(child);
    cv->validpix = 0;
    if (cv->screen_part.pixrect) {
	pr_destroy(cv->screen_part.pixrect);
	cv->screen_part.pixrect = 0;
    }
    if (cv->retained_part.pixrect && cv->transparent) {
	pr_destroy(cv->retained_part.pixrect);
	cv->retained_part.pixrect = 0;
    }
}

/* Creates the screen and retained pixrects for a canvas, if necessary */
cv_validate_pixrects(cv)
    register struct canvas *cv;
{
    if (cv == 0 || cv->validpix)
	return;
    cv_validate_pixrects(cv->parent);
    cv->validpix = 1;
    if (cv->parent && cv->parent->screen_part.pixrect && cv->mapped) {
	assert(cv->screen_part.pixrect == 0);
	if (cv->pos.x < cv->parent->screen_part.pixrect->pr_size.x
		&& cv->pos.y < cv->parent->screen_part.pixrect->pr_size.y)
	    cv->screen_part.pixrect =
		pr_region(cv->parent->screen_part.pixrect,
			  cv->pos.x, cv->pos.y,
			  cv->pixrect.pr_size.x, cv->pixrect.pr_size.y);
	else if (cv->retained_part.clip) {
	    sh_decref(cv->retained_part.clip);
	    cv->retained_part.clip = 0;
	}
	/* Compute screen position for cursor tracking tests */
	cv->scr_pos.x = cv->pos.x + cv->parent->scr_pos.x;
	cv->scr_pos.y = cv->pos.y + cv->parent->scr_pos.y;
    }
    if (cv->retained_part.pixrect == 0 && cv->retained)
	if (cv->transparent) {
	    if (cv->parent->retained_part.pixrect) {
		if (cv->pos.x < cv->parent->retained_part.pixrect->pr_size.x
		 && cv->pos.y < cv->parent->retained_part.pixrect->pr_size.y)
		    cv->retained_part.pixrect =
			pr_region(cv->parent->retained_part.pixrect,
				  cv->pos.x, cv->pos.y,
				  cv->pixrect.pr_size.x,
				  cv->pixrect.pr_size.y);
		else if (cv->retained_part.clip) {
		    sh_decref(cv->retained_part.clip);
		    cv->retained_part.clip = 0;
		}
	    }
	}
	else
	    cv_alloc_retained(cv, cv->pixrect.pr_size.x, cv->pixrect.pr_size.y,
			      cv->pixrect.pr_depth);
}

/*
 * Maps (makes visible) a canvas.  If savebits is false, the canvas image
 * becomes what was already there on the screen.
 */
cv_map(cv, savebits)
    register struct canvas *cv;
{
    if (cv->overlay || cv->mapped || !cv->map_req || !cv->parent->mapped)
	return;
    if (cv->validpix)
	cv_invalidate_pixrects(cv);
    cv->mapped = 1;
    cv_validate_pixrects(cv);
    if (!cv->transparent) {
	register struct shape *vp;
	vp = cv_compute_visible_part(cv, 0);
	cs_checkcursorcanvas(cv);
	if (cv->saveback && cv->next == 0 && cv->screen_part.pixrect) {
	    cv_alloc_retained(cv, cv->pixrect.pr_size.x, cv->pixrect.pr_size.y,
			      cv->pixrect.pr_depth);
	    if (cv->retained_part.pixrect) {
		pr_rop(cv->retained_part.pixrect, 0, 0,
		       cv->pixrect.pr_size.x, cv->pixrect.pr_size.y,
		       PIX_SRC, cv->screen_part.pixrect, 0, 0);
		if (GenerationDepth < 2)
		    GenerationDepth = 2;
		else {
		    GenerationDepth++;
		    if (GenerationDepth > 0xFF)
			GenerationDepth = 0xFF;
		}
		cv->subgeneration = GenerationDepth;
		InvalidationGeneration = GenerationDepth;
	    }
	    else {
		cv->saveback = 0;
		cv->subgeneration = 0;
	    }
	}
	else
	    cv->subgeneration = 0;
	if (vp) {
	    cv->mapped = 0;
	    cv_apply_to_intersecting_fragments_of_parent(cv->pos, vp, cv->parent,
							 0, cv_save_fragment);
	    cv->mapped = 1;
	    if (!cv->retained)
		cv_extend_damage(cv, vp);
	    else if (savebits)
		pr_shaperop(cv->screen_part.pixrect, vp, PIX_SRC,
			    cv->retained_part.pixrect, 0, 0);
	    sh_decref(vp);
	}
    }
#ifdef undef
    else {
	if (cv->retained_part.pixrect) {
	    pr_destroy(cv->retained_part.pixrect);
	    cv->retained_part.pixrect = 0;
	}
	if (cv->parent->retained_part.pixrect && cv->retained)
	    cv->retained_part.pixrect = pr_region(cv->parent->retained_part.pixrect,
						  cv->pos.x, cv->pos.y,
			       cv->pixrect.pr_size.x, cv->pixrect.pr_size.y);
    }
#endif
    cv_invalidate_clip(cv, 1);
    InvalidationGeneration = 0;
/*XX    if (cv->retained && !cv->hasopaque)
	cv->opaqparent->complete = 1; */
    for (cv = cv->topchild; cv; cv = cv->prev)
	cv_map(cv, 1);
}

int sh_only_apply_below;	/* If true, apply_to_intersecting_fragments
				   will only apply to fragments below the
				   ignored canvas.  Done as a global variable
				   to avoid perturbing existing callers of
				   cv_apply...: should be fixed someday */

/*
 * Iterates through canvas p and its children, from visual top to bottom; And
 * applies function F to any opaque canvases that intersect the shape "vp".
 * Each time it applies F, "vp" is reduced by the intersection.  The reduced
 * value of vp, after all applications of F, is returned.  If canvas "ignore"
 * is found, it is ignored, and "vp" is reduced by its shape
 */
struct shape *
cv_apply_to_intersecting_fragments(vp, p, ignore, F)
    register struct canvas *p,	/* Apply F to the opaque parts of F and its
				 * children that intersect vp */
               *ignore;		/* except for the ignored canvas */
    register struct shape *vp;	/* Visible part */
    int         (*F) ();
{
    register short T;
    struct spoint pos;
    register struct shape *i,
               *diff;
    i = sh_intersect(vp, p->outerclip);
    assert(vp == 0 || vp->is_rect || vp->trapset->refcnt > 0);
    if (i) {
	if (!p->validpix)
	    cv_validate_pixrects(p);
	if (p->hasopaque) {
	    register struct canvas *ccv;
	    struct spoint pos;
	    pos.x = 0;
	    pos.y = 0;
	    for (ccv = p->topchild; ccv && i; ccv = ccv->prev) {
		if (ccv->mapped
			&& !((T = pos.x + i->pos.x) >= ccv->pos.x + ccv->pixrect.pr_size.x
			     || T + i->size.x <= ccv->pos.x
			     || (T = pos.y + i->pos.y) >= ccv->pos.y + ccv->pixrect.pr_size.y
			     || T + i->size.y <= ccv->pos.y)
			&& (!ccv->transparent || ccv->hasopaque)) {
		    i = sh_translate(i, pos.x - ccv->pos.x, pos.y - ccv->pos.y);
    assert(i == 0 || i->is_rect || i->trapset->refcnt > 0);
    assert(ccv->outerclip == 0 || ccv->outerclip->is_rect || ccv->outerclip->trapset->refcnt > 0);
		    pos = ccv->pos;
		    if (overlap_possible(i, ccv->outerclip))
			if (ccv == ignore) {
			    register struct shape *tsh;
			    tsh = sh_difference(i, ccv->outerclip);
    assert(tsh == 0 || tsh->is_rect || tsh->trapset->refcnt > 0);
			    sh_decref(i);
			    i = tsh;
    assert(i == 0 || i->is_rect || i->trapset->refcnt > 0);
			}
			else if (!sh_only_apply_below)
			    i = cv_apply_to_intersecting_fragments(i, ccv,
								   ignore, F);
		}
		if (ccv == ignore)
		    sh_only_apply_below = 0;
	    }
	    i = sh_translate(i, pos.x, pos.y);
	}
	if (i) {
	    if (!p->validpix)
		cv_validate_pixrects(p);
	    (*F) (p, i);
	    cv_invalidate_clip(p, 0);
	    sh_decref(i);
	}
	diff = sh_difference(vp, p->outerclip);
	assert(vp->is_rect || vp->trapset->refcnt > 0);
	assert(diff == 0 || diff->is_rect || diff->trapset->refcnt > 0);
	sh_decref(vp);
	assert(diff == 0 || diff->is_rect || diff->trapset->refcnt > 0);
	vp = diff;
    }
    sh_only_apply_below = 0;
    return vp;
}

/*
 * Invokes cv_apply_to_intersecting_fragments starting at the opaque parent of
 * p. "vp" will be translated by "pos"
 */
cv_apply_to_intersecting_fragments_of_parent(pos, vp, p, ignore, F)
    struct spoint pos;
    register struct canvas *p,
               *ignore;
    register struct shape *vp;
    int         (*F) ();
{
    if (vp == 0)
	return;
    sh_incref(vp);
    while (p != p->opaqparent) {
	pos.x += p->pos.x;
	pos.y += p->pos.y;
	p = p->parent;
    }
    vp = cv_apply_to_intersecting_fragments(sh_translate(vp, pos.x, pos.y), p,
					    ignore, F);
    /*- assert(vp == 0); */
    if (vp)
	sh_decref(vp);
}

/*
 * Inserts canvas "cv" in the hierarchy above "after" with the specified x,y
 * coordinates.  If cv isn't already in the hierarchy & mapped, then this is
 * the same as cv_insert.  Otherwise it is a movement of a visible canvas in
 * x, y, and z.  cs_intercanvasabove tries to do this with a minimal amount of
 * ropping.  It first saves the fragments that are about to be covered by
 * "cv".  Then it copies the bits of cv that are on the screen and that will
 * remain on the screen,  Finally it restores, or marks as damaged, the pieces
 * that become exposed
 */
cs_insertcanvasabove(cv, after, x, y)
    register struct canvas *cv,
               *after;
{
    struct spoint oldpos,
                newpos;
    struct canvas *oldprev = cv->prev,
               *oldnext = cv->next;
    struct canvas *newprev,
               *newnext;
    struct shape *newvis,
               *oldvis;
    struct shape *sh,
               *both;
    struct pixrect *old;
    if (after == cv && (after = cv->prev) == 0)
	if (cv->mapped || (after = cv->parent->topchild) == 0
		|| after == cv)
	    after = cv->parent;
    if (after == 0)
	return;
    cs_cursordown();		/* Punt and remove cursor on entire screen */
    assert(after == cv->parent || after->parent == cv->parent);
    /*
     * The following four lines should not be here.  They are quick hack to
     * get around a bug in the pixrect spec.  After the revolution, this will
     * be fixed.  The bug is that with pixrects, you can't call pr_region with
     * a negative x or y in the origin.
     */
    if (x < 0)
	x = 0;
    if (y < 0)
	y = 0;
    assert(cv->parent);
    if (cv->scene == 0 || cv->scene != after->scene
	    || !cv->mapped || cv->transparent) {
	struct canvas *oldparent;
	if (oldparent = cv->parent) {
	    cv_incref(oldparent);	/* cs_remove does a decref */
	    cs_remove(cv, 1);
	    cv->parent = oldparent;
	}
	cv->pos.x = x;
	cv->pos.y = y;
	cv_insert(cv, after, 1);
	return;
    }
    if (cv->pos.x == x && cv->pos.y == y && cv->prev == after)
	return;
    if (cv->hasopaque) {
	register struct canvas *p;
	for (p = cv->topchild; p; p = p->prev)
	    cv_unmap(p, 1);
    }
    cv->invgeneration = 0;
    cv->opaqparent->invgeneration = 0;
    /* compute the old shape */
    oldvis = cv_compute_visible_part(cv, 0);
    if (after == cv->parent) {
	newprev = 0;
	newnext = cv->parent->topchild;
	if (newnext)
	    while (newnext->prev)
		newnext = newnext->prev;
    }
    else {
	newprev = after;
	newnext = after->next;
    }
    if (newnext == cv)
	newnext = cv->next;
    if (oldprev)
	oldprev->next = oldnext;
    if (oldnext) {
	assert(oldnext != oldprev);
	oldnext->prev = oldprev;
    }
    oldpos = cv->pos;
    newpos.x = x;
    newpos.y = y;
    cv->pos = newpos;
    cv_invalidate_clip(cv, 1);
    cv->next = newnext;
    /* Compute the new shape */
    newvis = cv_compute_visible_part(cv, 0);
    cv->next = oldnext;
    /*
     * newvis is the shape that is visible in the new position, relative to
     * the new position
     */
    cv->pos = oldpos;
    if (oldprev)
	oldprev->next = cv;
    if (oldnext) {
	oldnext->prev = cv;
	assert(oldnext != cv);
    }
    /*
     * save the fragments that are about to be covered
     */
    cv_apply_to_intersecting_fragments_of_parent(newpos, newvis, cv->parent,
						 cv, cv_save_fragment);

    /* Link the canvas into its new place */
    if (oldprev)
	oldprev->next = oldnext;
    if (oldnext) {
	assert(oldnext != oldprev);
	oldnext->prev = oldprev;
    }
    else {
	assert(oldprev == 0 || cv->parent == oldprev->parent);
	cv->parent->topchild = oldprev;
    }
    if (cv->prev = newprev) {
	assert(cv != newprev);
	newprev->next = cv;
    }
    if (cv->next = newnext) {
	newnext->prev = cv;
	assert(newnext != cv);
    }
    else
	cv->parent->topchild = cv;

    assert(newvis == 0 || newvis->refcnt > 0);
    old = cv->screen_part.pixrect;
    cv->screen_part.pixrect = 0;
    cv_invalidate_pixrects(cv);
    cv->pos = newpos;
    cv_validate_pixrects(cv);
    both = 0;
    /* Copy the bits of the moving canvas */
    if (cv->complete || ((both = sh_intersect(newvis, oldvis))
			 && !both->is_rect
			 && cv->retained
			 && (newpos.x != oldpos.x || newpos.y != oldpos.y))) {
	if (!cv->complete  && cv->retained_part.pixrect) {
	    pr_shaperop(cv->retained_part.pixrect, oldvis, PIX_SRC,
			old, 0, 0);
/*XX	    cv->complete = 1; */
	}
	assert(newvis == 0 || newvis->refcnt > 0);
	if (newvis && cv->screen_part.pixrect)
	    pr_shaperop(cv->screen_part.pixrect, newvis, PIX_SRC,
			cv->retained_part.pixrect, 0, 0);
	if (both)
	    sh_decref(both);
    }
    else {
	static struct spoint zero = {0, 0};
	int         moving = newpos.x != oldpos.x || newpos.y != oldpos.y;
	if (cv->retained
		&& (sh = sh_difference(oldvis, newvis))) {
	    pr_shaperop(cv->retained_part.pixrect, sh, PIX_SRC, old, 0, 0);
	    sh_decref(sh);
	}
	assert(newvis == 0 || newvis->refcnt > 0);
	if (both && (both->is_rect || !moving /* || both->trapset->next == 0 */ )) {
	    if (moving)
		pr_shaperop(cv->screen_part.pixrect, both, PIX_SRC, old, 0, 0);
	    sh = sh_difference(newvis, oldvis);
	}
	else {
	    sh = newvis;
	    if (sh)
		sh_incref(sh);
	}
	if (both)
	    sh_decref(both);
	assert(newvis == 0 || newvis->refcnt > 0);
	if (sh) {
	    cv_apply_to_intersecting_fragments_of_parent(zero, sh, cv,
						     0, cv_restore_fragment);

#ifdef undef
	    if (cv->retained)
		pr_shaperop(cv->screen_part.pixrect, sh,
			    PIX_SRC, cv->retained_part.pixrect, 0, 0);
	    else
		cv_extend_damage(cv, sh);
#endif

	    sh_decref(sh);
	}
    }
    if (old)
	pr_destroy(old);
    newvis = sh_translate(newvis, newpos.x - oldpos.x, newpos.y - oldpos.y);
    assert(newvis == 0 || newvis->refcnt > 0);
    sh = sh_difference(oldvis, newvis);	/* the uncovered part */
    assert(newvis == 0 || newvis->refcnt > 0);
    /* restore the pieces that are uncovered */
    if (sh) {
	cv->mapped = 0;
	cv_apply_to_intersecting_fragments_of_parent(oldpos, sh, cv->parent,
						     0, cv_restore_fragment);
	cv->mapped = 1;
	sh_decref(sh);
    }
    if (newvis)
	sh_decref(newvis);
    if (oldvis)
	sh_decref(oldvis);
    cv->scene = after->scene;
    if (cv->hasopaque) {
	register struct canvas *p;
	for (p = cv->topchild; p; p = p->prev)
	    cv_map(p, 1);
    }
    assert(cv->mapped);
}

/* Invalidate the clip cache information for canvas cv and its descendants */
cv_invalidate_clip(cv, include_opaque)
    register struct canvas *cv;
{
    register struct canvas *child;
    if (cv->lastclip != &InvalidShape) {
	if (cv->lastclip)
	    sh_decref(cv->lastclip);
	cv->lastclip = &InvalidShape;
    }
    cv->opaqparent->invgeneration = InvalidationGeneration;
    cv->invgeneration = InvalidationGeneration;
    cv->pixrect.pr_ops = &cv_ops;
    for (child = cv->topchild; child; child = child->prev)
	if (child->transparent || include_opaque) {
	    assert(child->parent == cv);
	    cv_invalidate_clip(child, include_opaque);
	}
}

/* Find the offset of canvas "cv" relative to the framebuffer */
cv_findcanvasoffset(cv)
    register struct canvas *cv;
{
    shape_point.x = 0;
    shape_point.y = 0;
    while (cv) {
	cfloorfr(shape_point.x) += cv->pos.x;
	cfloorfr(shape_point.y) += cv->pos.y;
	cv = cv->parent;
    }
}

scene_initialize () {
    subgeneration = 99;
}