#include "i.h"

typedef struct Fontinfo Fontinfo;
typedef struct Colornode Colornode;
typedef struct Source Source;
typedef struct Shtml Shtml;
typedef struct Simage Simage;
typedef struct Sources Sources;

struct Fontinfo
{
	char*	name;
	Font*	f;
	int		spw;		// width of a space in this font
};

// Seems better to use a slightly smaller font in Controls, to match other browsers
enum { CtlFnt = FntR*NumSize+Small };

// color stuff.  have hash table mapping RGB values to Image for that color
struct Colornode
{
	int			rgb;
	Image*		im;
	Colornode*	next;
};

// Source of info for page (html, image, etc.)
struct Source
{
	Source*		next;			// in list of source for a page
	ByteSource*	bs;
	int			redirects;
	int			tag;			// Shtmltag or Simagetag
};


struct Shtml
{
	Source*		next;			// in list of source for a page
	ByteSource*	bs;
	int			redirects;
	int			tag;			// Shtmltag
	ItemSource*	itsrc;
};


struct Simage
{
	Source*		next;			// in list of source for a page
	ByteSource*	bs;
	int			redirects;
	int			tag;			// Simagetag
	CImage*		ci;
	Itemlist*		itl;
	ImageSource*	imsrc;
};

enum { Shtmltag, Simagetag };


struct Sources
{
	Source*	srcs;
	int	tot;
	int	done;
};

enum {
	NCOLHASH = 19,	// 19 checked for standard colors: only 1 collision
	TABPIX = 30,		// number of pixels in a tab
	CAPSEP = 5,		// number of pixels separating tab from caption
	SCRBREADTH = 20,	// scrollbar breadth (normal)
	SCRFBREADTH = 14,	// scrollbar breadth (inside child frame or select control)
	FRMARGIN = 10,	// default margin around frames
	RULESP = 7,		// extra space before and after rules
	CBOXWID = 14,		// check box width
	CBOXHT = 12,		// check box height
	ENTVMARGIN = 4,	// vertical margin inside entry box
	ENTHMARGIN = 6,	// horizontal margin inside entry box
	SELMARGIN = 4,	// margin inside select control
	BUTMARGIN = 4,	// margin inside button control
	PBOXWID = 16,		// progress box width
	PBOXHT = 16,		// progress box height
	SELBG = 0x00FFFF,	// aqua
	CTRLMASK = 0x1F,
	DEL = 0x7F,
	TAB = '\t',
	CR = '\n',
	TABLEMAXTARGET = 2000,	// targetwidth to get max width of table cell
	TABLEFLOATTARGET = 600,	// targetwidth for floating tables
};

// triangle shapes
enum { TRIup, TRIdown, TRIleft, TRIright };

Fontinfo	fonts[NumFnt]= {
	{"/lib/font/bit/lucidasans/unicode.6.font", nil, 0},
	{"/lib/font/bit/lucidasans/unicode.7.font", nil, 0},
	{"/lib/font/bit/lucidasans/unicode.8.font", nil, 0},
	{"/lib/font/bit/lucidasans/unicode.10.font", nil, 0},
	{"/lib/font/bit/lucidasans/unicode.13.font", nil, 0},
	{"/lib/font/bit/lucidasans/italicunicode.6.font", nil, 0},
	{"/lib/font/bit/lucidasans/italicunicode.7.font", nil, 0},
	{"/lib/font/bit/lucidasans/italicunicode.8.font", nil, 0},
	{"/lib/font/bit/lucidasans/italicunicode.10.font", nil, 0},
	{"/lib/font/bit/lucidasans/italicunicode.13.font", nil, 0},
	{"/lib/font/bit/lucidasans/boldunicode.6.font", nil, 0},
	{"/lib/font/bit/lucidasans/boldunicode.7.font", nil, 0},
	{"/lib/font/bit/lucidasans/boldunicode.8.font", nil, 0},
	{"/lib/font/bit/lucidasans/boldunicode.10.font", nil, 0},
	{"/lib/font/bit/lucidasans/boldunicode.13.font", nil, 0},
	{"/lib/font/bit/lucidasans/typeunicode.6.font", nil, 0},
	{"/lib/font/bit/lucidasans/typeunicode.7.font", nil, 0},
	{"/lib/font/bit/lucidasans/typeunicode.9.font", nil, 0},
	{"/lib/font/bit/lucidasans/typeunicode.12.font", nil, 0},
	{"/lib/font/bit/lucidasans/typeunicode.16.font", nil, 0}
};

Colornode*	colorhashtab[19];

uchar	wordchar[0xA0]= {
	['0']  1, ['1']  1, ['2']  1, ['3']  1, ['4']  1,
	['5']  1, ['6']  1, ['7']  1, ['8']  1, ['9']  1,
	['A']  1, ['B']  1, ['C']  1, ['D']  1, ['E']  1, ['F']  1,
	['G']  1, ['H']  1, ['I']  1, ['J']  1, ['K']  1, ['L']  1,
	['M']  1, ['N']  1, ['O']  1, ['P']  1, ['Q']  1, ['R']  1,
	['S']  1, ['T']  1, ['U']  1, ['V']  1, ['W']  1, ['X']  1,
	['Y']  1, ['Z']  1,
	['a']  1, ['b']  1, ['c']  1, ['d']  1, ['e']  1, ['f']  1,
	['g']  1, ['h']  1, ['i']  1, ['j']  1, ['k']  1, ['l']  1,
	['m']  1, ['n']  1, ['o']  1, ['p']  1, ['q']  1, ['r']  1,
	['s']  1, ['t']  1, ['u']  1, ['v']  1, ['w']  1, ['x']  1,
	['y']  1, ['z']  1,
	['_']  1,
	['\'']  1, ['"']  1, ['.']  1, [',']  1, ['(']  1, [')']  1
};

int	dbglay = 0;
int	dbgtab = 0;

static int	linespace = 0;
static int	lineascent = 0;
static int	charspace = 0;
static int	spspace = 0;
static int	ctllinespace = 0;
static int	ctllineascent = 0;
static int	ctlcharspace = 0;
static int	ctlspspace = 0;
static int	frameid = 0;

static int	addsubords(Sources* sources, Docinfo* di, Rune* auth);
static Sources* newsources(void);
static void	addsource(Sources* srcs, Source* s);
static Source*	newshtml(ByteSource* bs, ItemSource* is);
static Source*	newsimage(ByteSource* bs, CImage* ci, ImageSource* is);
static Source*	copysource(Source* s);
static Source*	findbs(Sources* srcs, ByteSource* bs);
static void	startimreq(Simage* s, Rune* auth);
static void	createvscroll(Frame* f);
static void	createhscroll(Frame* f);
static void	fixframegeom(Frame* f);
static void	haveimage(Frame* f, CImage* ci, Itemlist* itl);
static Lay* sublayout(Frame* f, int targetwidth, uchar just, Background bg, Item* content);
static void	relayout(Frame* f, Lay* lay, int targetwidth, int just);
static void	appenditems(Frame* f, Lay* lay, Item* items);
static void	fixgeom(Frame* f, Lay* lay, Line* l);
static void	fixlinegeom(Frame* f, Lay* lay, Line* l);
static int	pastbrk(Lay* lay, int y, int state);
static void	appendline(Line* lprev, Line* l);
static void	changelines(Line* l, Line* lend);
static Font*	getfont(int num);
static void	measure(Frame* fr, Item* items);
static void	setimagedims(Iimage* i);
static void	updatelgeom(int* pH, int* pA, Item* it);
static int	trybreak(Item* bit, int availw, int* piw, int noneok);
static int	breakstring(Rune* s, int sw, Font* fnt, int availw, int noneok, Rune** ps1, int* pw1, Rune** ps2, int* pw2);
static int	wrapstring(Font* fnt, Rune* s, int availw, Rune*** plines, int** plinestarts);
static int	breakpoint(Rune* s, int slen, int i, int incr);
static int	tryw(Font* fnt, Rune* s, int i, Rune** pss);
static int	floatw(int ymin, int ymax, Ifloat* flist, uchar side);
static void	fixfloatxy(Lay* lay, int y, Ifloat* f);
static void	fixfloatsafter(Lay* lay, Line* l, List* flist);
static int	floatclry(Ifloat* flist, uchar side, int y);
static void	sizetable(Frame* f, Table* tab, int availwidth);
static void	tableparams(Table* tab, int* hsp, int* vsp, int* pad, int* bd, int* cbd, int* hsep, int* vsep);
static int	cellwidth(Table* tab, Tablecell* c, int hsep);
static int	cellheight(Table* tab, Tablecell* c, int vsep);
static int	widthcalc(Table* tab, int* w, int hsep, int domax);
static void	layframeset(Frame* f, Kidinfo* ki);
static int	frdimens(Dimen* dims, int n, int t, int** parr);
static Item*	lastitem(Item* it);
static void	checktabsize(Frame* f, Itable* t, int availw);
static int	widthfromspec(Dimen wspec, int availw);
static void	checkffsize(Frame* f, Item* i, Formfield* ff);
static void	drawall(Frame* f);
static void	drawlay(Frame* f, Lay* lay, Point origin);
static void	drawline(Frame* f, Point layorigin, Line* l, Lay* lay);
static void	drawimg(Frame* f, Point iorigin, Iimage* i);
static void	drawtable(Frame* f, Lay* parentlay, Point torigin, Table* tab);
static void	markchanges(Loc* loc);
static Image*	colorimage(int rgb);
static Colornode*	newcolornode(int rgb, Image* im, Colornode* next);
static void	fillbg(Frame* f, Rectangle r);
static void	drawtriangle(Image* im, Rectangle r, int kind, int style);
static void	flushc(Frame* f);
static Loc*	framefind(Loc* loc, Frame* f, Point p, Item* it);
static Loc*	layfind(Loc* loc, Frame* f, Lay* lay, Point origin, Point p, Item* it);
static Loc*	linefind(Loc* loc, Frame* f, Line* l, Point o, Point p, Item* it);
static Loc*	tablefind(Loc* loc, Frame* f, Itable* ti, Point torigin, Point p, Item* it);
static void	entrydelrange(Centry* e, int istart, int iend);
static void	entrysetfromsnarf(Centry* e);
static int	entrywrapcalc(Centry* e, int** plinestarts, int* ptopline, int* pcursline);
static void	entryscroll(Centry* e);
static void	animproc(void *arg);

void
layoutinit()
{
	Font*	fnt;

	// make sure default and control fonts are loaded
	getfont(DefFnt);
	fnt = fonts[DefFnt].f;
	linespace = fnt->height;
	lineascent = fnt->ascent;
	charspace = runestringwidth(fnt, L"a");
	spspace = fonts[DefFnt].spw;
	getfont(CtlFnt);
	fnt = fonts[CtlFnt].f;
	ctllinespace = fnt->height;
	ctllineascent = fnt->ascent;
	ctlcharspace = runestringwidth(fnt, L"a");
	ctlspspace = fonts[CtlFnt].spw;
}

// Use bsmain to fill frame f, and free bsmain.
// Return buffer containing source in *pbuf and return its length.
//
// An important invariant is that we keep
// track of every ByteSource returned by startreq, and
// ensure that we freebs each of them.
int
layout(Frame* f, ByteSource* bsmain, uchar** pbuf)
{
	Sources*	sources;
	Header*	hdr;
	Rune*	auth;
	uchar*	ans;
	int		anslen;
	Docinfo*	di;
	Lay*	l;
	int	anyanim;
	ItemSource*	itsrc;
	ImageSource*	imsrc;
	CImage*	ci;
	CImage*	newci;
	Item*	it;
	Iimage*	ii;
	Itemlist*	itl;
	Source*	news;
	Simage*	sim;
	Shtml*	sh;
	Source*	s;
	int	use;
	int	error;
	Rune*	challenge;
	ParsedUrl*	newurl;
	int	n;
	int	ret;
	MaskedImage*	mim;
	ByteSource*	bs;
	Source*	src;
	int	freeit;
	void*	animargs[1];

	dbglay = config.dbg['l'];
	dbgtab = config.dbg['t'];
	if(pbuf)
		*pbuf = nil;
	if(dbgev)
		logtime("LAYOUT", 0);
	sources = newsources();
	hdr = bsmain->hdr;
	auth = bsmain->req->auth;
	ans = nil;
	anslen = 0;
	di = newdocinfo();
	resetframe(f);
	f->doc = di;
	di->frameid = f->id;
	di->src = hdr->actual;
	di->base = hdr->base;
	di->refresh = hdr->refresh;
	di->chset = hdr->chset;
	if(f->framebd != 0) {
		f->cr = insetrect(f->r, 2);
		drawborder(f->cim, f->cr, 2, DarkGrey);
	}
	fillbg(f, f->cr);
	flushc(f);
	if(f->flags&FRvscroll)
		createvscroll(f);
	if(f->flags&FRhscroll)
		createhscroll(f);
	l = newlay(Dx(f->cr), ALleft, f->marginw, di->background);
	f->layout = l;
	anyanim = 0;
	if(hdr->mtype == TextHtml || hdr->mtype == TextPlain) {
		itsrc = newitemsource(bsmain, di, hdr->mtype);
		addsource(sources, newshtml(bsmain, itsrc));
	}
	else {
		if(!supported(hdr->mtype)) {
			trace("Need to implement something: source isn't supported image type\n");
			return 0;
		}
		imsrc = newimagesource(bsmain, 0, 0);
		ci = newcimage(bsmain->req->url, 0, 0);
		s = newsimage(bsmain, ci, imsrc);
		addsource(sources, s);
		it = newiimage(nil, nil, ALbottom, 0, 0, 0, 0, 0, 0, nil);
		ii = (Iimage*)it;
		ii->ci = ci;
		di->images = ii;
		appenditems(f, l, it);
		((Simage*)s)->itl = newitemlist(it, nil);
	}
	while(sources->done < sources->tot) {
		if(dbgev)
			logtime("LAYOUT GETSOMETHING", 0);
		bs = waitreq();
		if(bs == nil)
			break;		/* abort condition propagated by netget */
		src = findbs(sources, bs);
		// if(src == nil)
		//	continue;
		assert(src != nil);
		freeit = 0;
		if(bs->err) {
			if(dbglay)
				trace("error getting something: %S\n", errphrase(bs->err));
			freeit = 1;
		}
		else {
			if(bs->hdr != nil && !bs->seenhdr) {
				use = hdraction(bs, 0, src->redirects, &error, &challenge, &newurl);
				if(challenge != nil) {
					trace("Need to implement authorization credential dialog\n");
					error = ERRauthfailed;
					use = 0;
				}
				if(error && dbglay)
					trace("subordinate error: %S\n", errphrase(error));
				if(newurl != nil) {
					// redirect
					freeit = 1;
					switch(src->tag) {
					case Shtmltag:
						trace("unexpected redirect of subord\n");
						break;
					case Simagetag:
						sim = (Simage*)src;
						newci = newcimage(newurl, sim->ci->width, sim->ci->height);
						for(itl = sim->itl; itl != nil; itl = itl->next) {
							it = itl->val;
							assert(it->tag == Iimagetag);
							((Iimage*)it)->ci = newci;
						}
						news = newsimage(nil, newci, nil);
						((Simage*)news)->itl = sim->itl;
						addsource(sources, news);
						startimreq((Simage*)news, auth);
						break;
					}
				}
				if(!use)
					freeit = 1;
			}
			if(!freeit && bs->edata > bs->lim) {
				switch(src->tag) {
				case Shtmltag:
					sh = (Shtml*)src;
					it = getitems(sh->itsrc);
					if(bs == bsmain) {
						if(di->kidinfo != nil) {
							if(sh->itsrc->kidstk == nil) {
								layframeset(f, di->kidinfo);
								flushimage(display, 1);
								freeit = 1;
							}
						}
						else {
							l->background = di->background;
							anyanim |= addsubords(sources, di, auth);
							if(it != nil) {
								appenditems(f, l, it);
								fixframegeom(f);
								if(dbgev)
									logtime("LAYOUT_DRAWALL", 0);
								drawall(f);
							}
						}
					}
					else {
						trace("Need to implement embedded html objects\n");
						freeit = 1;
					}
					break;
				case Simagetag:
					sim = (Simage*)src;
					ret = getmim(sim->imsrc, &mim);
					if(ret == Mimerror) {
						freeit = 1;
					}
					else if(ret != Mimnone) {
						if(sim->ci->mims == nil) {
							sim->ci->mims = (MaskedImage**)emalloc(sizeof(MaskedImage*));
							sim->ci->mimslen = 1;
							sim->ci->mims[0] = mim;
							sim->ci->width = sim->imsrc->width;
							sim->ci->height = sim->imsrc->height;
							if(ret == Mimdone && config.imagelvl <= ImgNoAnim)
								freeit = 1;
						}
						else {
							n = sim->ci->mimslen;
							if(mim != sim->ci->mims[n - 1]) {
								sim->ci->mims = (MaskedImage**)erealloc(sim->ci->mims, (n+1)*sizeof(MaskedImage*));
								sim->ci->mims[sim->ci->mimslen++] = mim;
								anyanim = 1;
							}
						}
						if(sim->ci->mims[0] == mim)
							haveimage(f, sim->ci, sim->itl);
						if(bs->lim == bs->hdr->length)
							imcacheadd(sim->ci);
					}
					break;
				}
			}
			if(!freeit && bs->hdr != nil && bs->lim == bs->hdr->length)
				freeit = 1;
		}
		if(freeit) {
			if(bs == bsmain) {
				ans = bs->data;
				anslen = bs->edata;
			}
			freebs(bs);
			src->bs = nil;
			sources->done++;
		}
	}
	if(anyanim && config.imagelvl > ImgNoAnim) {
		animargs[0] = f;
		proccreate(animproc, animargs, STACKSIZE);
	}
	if(dbgev)
		logtime("LAYOUT_END", 0);
	if(pbuf)
		*pbuf = ans;
	return anslen;
}

// return value is 1 if found any existing images needed animation
static int
addsubords(Sources* sources, Docinfo* di, Rune* auth)
{
	int	anyanim;
	List*	newsims;
	int	iciw;
	int	icih;
	Source*	s;
	Simage*	sim;
	CImage*	cachedci;
	Iimage*	i;

	anyanim = 0;
	if(config.imagelvl == ImgNone)
		return anyanim;
	newsims = nil;
	for(i = di->images; i != nil; i = i->nextimage) {
		if(i->ci->mims == nil) {
			cachedci = imcachelook(i->ci);
			if(cachedci != nil) {
				i->ci = cachedci;
				if(i->imwidth == 0)
					i->imwidth = i->ci->width;
				if(i->imheight == 0)
					i->imheight = i->ci->height;
				anyanim |= (cachedci->mimslen > 1);
				if(i == di->backgrounditem)
					di->background.image = i->ci;
			}
			else {
				for(s = sources->srcs; s != nil; s = s->next) {
					if(s->tag == Simagetag) {
						sim = (Simage*)s;
						if(cimagematch(sim->ci, i->ci)) {
							sim->itl = newitemlist((Item*)i, sim->itl);
							// want all items on list to share same ci;
							// want most-specific dimension specs
							iciw = i->ci->width;
							icih = i->ci->height;
							i->ci = sim->ci;
							if(sim->ci->width == 0 && sim->ci->height == 0) {
								sim->ci->width = iciw;
								sim->ci->height = icih;
							}
							break;
						}
					}
				}
				if(s == nil) {
					// didn't find existing Source for this image
					s = newsimage(nil, i->ci, nil);
					((Simage*)s)->itl = newitemlist((Item*)i, nil);
					newsims = newlist((int)s, newsims);
					addsource(sources, s);
				}
			}
		}
	}
	for( ; newsims != nil; newsims = newsims->next) {
		startimreq((Simage*)(newsims->val), auth);
	}
	return anyanim;
}

static void
startimreq(Simage* s, Rune* auth)
{
	ByteSource*	bs;

	if(dbgev)
		logtime("LAYOUT STARTREQ", 0);
	bs = startreq(newreqinfo(s->ci->src, HGet, nil, 0, auth, FTself));
	s->bs = bs;
	s->imsrc = newimagesource(bs, s->ci->width, s->ci->height);
}

static void
createvscroll(Frame* f)
{
	int	breadth;
	int	length;

	breadth = SCRBREADTH;
	if(f->parent != nil)
		breadth = SCRFBREADTH;
	length = Dy(f->cr);
	if(f->flags&FRhscroll)
		length -= breadth;
	f->vscr = newscroll(f, 1, length, breadth);
	f->vscr->r = rectaddpt(f->vscr->r, f->cr.min);
	f->cr.min.x += breadth;
	if(Dx(f->cr) <= 2*f->marginw)
		trace("botch: frame too small for layout");
	else
		drawctl(f->vscr, 0);
}

static void
createhscroll(Frame* f)
{
	int	breadth;
	int	length;
	int	x;

	breadth = SCRBREADTH;
	if(f->parent != nil)
		breadth = SCRFBREADTH;
	length = Dx(f->cr);
	x = f->cr.min.x;
	f->hscr = newscroll(f, 0, length, breadth);
	f->hscr->r = rectaddpt(f->hscr->r, Pt(x, f->cr.max.y - breadth));
	f->cr.max.y -= breadth;
	if(Dy(f->cr) <= 2*f->marginh)
		trace("botch: frame too small for layout");
	else
		drawctl(f->hscr, 0);
}

// Call after a change to f.layout or f.viewr.min to fix totalr and viewr
// (We are to leave viewr.min unchanged, if possible, as
// user might be scrolling).
static void
fixframegeom(Frame* f)
{
	Lay*	l;
	int	crwidth;
	int	crheight;
	int	crchanged;
	int	n;

	l = f->layout;
	if(dbglay)
		trace("fixframegeom, layout width=%d, height=%d\n", l->width, l->height);
	f->totalr.max = Pt(l->width, l->height);
	crwidth = Dx(f->cr);
	crheight = Dy(f->cr);
	crchanged = 0;
	n = l->height + l->margin - crheight;
	if(n > 0 && f->vscr == nil && (f->flags&FRvscrollauto)) {
		createvscroll(f);
		crchanged = 1;
		crwidth = Dx(f->cr);
	}
	if(f->viewr.min.y > n)
		f->viewr.min.y = max(0, n);
	n = l->width + l->margin - crwidth;
	if(n > 0 && f->hscr == nil && (f->flags&FRhscrollauto)) {
		createhscroll(f);
		crchanged = 1;
		crheight = Dy(f->cr);
	}
	if(crchanged) {
		relayout(f, l, crwidth, l->just);
		fixframegeom(f);
		return ;
	}
	if(f->viewr.min.x > n)
		f->viewr.min.x = max(0, n);
	f->viewr.max.x = min(f->viewr.min.x + crwidth, l->width);
	f->viewr.max.y = min(f->viewr.min.y + crheight, l->height);
	if(f->vscr != nil)
		scrollset(f->vscr, f->viewr.min.y, f->viewr.max.y, f->totalr.max.y, 5);
	if(f->hscr != nil)
		scrollset(f->hscr, f->viewr.min.x, f->viewr.max.x, f->totalr.max.x, 5);
}

// The items its within f are Iimage items,
// and its image, ci, now has at least a ci->mims[0], which may be partially
// or fully filled.
static void
haveimage(Frame* f, CImage* ci, Itemlist* itl)
{
	int	dorelayout;
	Image*	im;
	Ifloat*	fit;
	Item*	locit;
	int	k;
	Loc*	loc;
	Iimage*	i;
	Item*	it;

	if(dbgev)
		logtime("HAVEIMAGE", 0);
	if(dbglay)
		trace("\nHAVEIMAGE src=%S w=%d h=%d\n", ci->src->url, ci->width, ci->height);
	for(dorelayout = 0; itl != nil; itl = itl->next) {
		it = itl->val;
		switch(it->tag) {
		case Iimagetag:
			i = (Iimage*)it;
			if(it == (Item*)f->doc->backgrounditem && f->doc->background.image == nil) {
				im = ci->mims[0]->im;
				im->repl = 1;
				im->clipr = Rect(-0x3FFFFFFF, 0x3FFFFFFF, -0x3FFFFFFF, 0x3FFFFFFF);
				f->doc->background.image = i->ci;
			}
			else {
				// If i->imwidth and i->imheight are not both 0, the HTML specified the dimens.
				// If one of them is 0, the other is to be scaled by the same factor;
				// we have to relay the line in that case too.
				if(i->imwidth == 0 || i->imheight == 0) {
					i->imwidth = ci->width;
					i->imheight = ci->height;
					setimagedims(i);
					loc = findloc(f, ZP, it);
					// sometimes the image was added to doc image list, but
					// never made it to layout (e.g., because html bug prevented
					// a table from being added).
					// also, script-created images won't have items
					if(loc != nil) {
						markchanges(loc);
						dorelayout = 1;
						// Floats are assumed to be premeasured, so if there
						// are any floats in the loc list, remeasure them
						for(k = loc->n - 1; k > 0; k--) {
							if(loc->le[k].kind == LEitem) {
								locit = loc->le[k].item;
								switch(locit->tag) {
								case Ifloattag:
									fit = (Ifloat*)locit;
									switch(fit->item->tag) {
									case Iimagetag:
										fit->height = fit->item->height;
										break;
									case Itabletag:
										checktabsize(f, (Itable*)fit->item, TABLEFLOATTARGET);
										break;
									}
									break;
								}
							}
						}
					}
				}
			}
			if(dbg > 1)
				trace("\nhaveimage item: %I", it);
			break;
		}
	}
	if(dorelayout) {
		relayout(f, f->layout, f->layout->targetwidth, f->layout->just);
		fixframegeom(f);
	}
	drawall(f);
	if(dbgev)
		logtime("HAVEIMAGE_END", 0);
}

// For first layout of subelements, such as table cells.
// After this, content items will be dispersed throughout resulting lay.
// Return the new layout.
static Lay*
sublayout(Frame* f, int targetwidth, uchar just, Background bg, Item* content)
{
	Lay*	l;

	if(dbglay)
		trace("sublayout, targetwidth=%d\n", targetwidth);
	l = newlay(targetwidth, just, 0, bg);
	appenditems(f, l, content);
	l->flags &= ~Lchanged;
	if(dbglay)
		trace("after sublayout, width=%d\n", l->width);
	return l;
}

// Relayout of lay, given a new target width or if something changed inside
// or if the global justification for the layout changed.
// Floats are hard: for now, just relay everything with floats temporarily
// moved way down, if there are any floats.
static void
relayout(Frame* f, Lay* lay, int targetwidth, int just)
{
	int	changeall;
	Ifloat*	ff;

	if(dbglay)
		trace("relayout, targetwidth=%d, old target=%d, changed=%d\n", targetwidth, lay->targetwidth, (lay->flags&Lchanged) != (uchar)0);
	changeall = (lay->targetwidth != targetwidth || lay->just != just);
	if(!changeall && !(lay->flags&Lchanged))
		return ;
	if(lay->floats != nil) {
		for(ff = lay->floats; ff != nil; ff = ff->nextfloat)
			ff->y = 0x6fffffff;
		changeall = 1;
	}
	lay->targetwidth = targetwidth;
	lay->just = just;
	lay->width = 0;
	if(changeall)
		changelines(lay->start->next, lay->end);
	fixgeom(f, lay, lay->start->next);
	lay->flags &= ~Lchanged;
	if(dbglay)
		trace("after relayout, width=%d\n", lay->width);
}

// Measure and append the items to the end of layout lay,
// and fix the geometry.
static void
appenditems(Frame* f, Lay* lay, Item* items)
{
	Item*	it;
	Line*	lprev;
	Line*	l;
	Item*	lit;
	Item*	nexti;

	measure(f, items);
	if(dbglay)
		printitems(items, "appenditems, after measturetexts");
	it = items;
	if(it == nil)
		return ;
	lprev = lay->end->prev;
	lit = lastitem(lprev->items);
	if(lit == nil || (it->state&IFbrk)) {
		// start a new line after existing last line
		l = newline();
		appendline(lprev, l);
		l->items = it;
	}
	else {
		// start appending items to existing last line
		l = lprev;
		lit->next = it;
	}
	l->flags |= Lchanged;
	while(it != nil) {
		nexti = it->next;
		if(nexti == nil || (nexti->state&IFbrk)) {
			it->next = nil;
			fixgeom(f, lay, l);
			if(nexti == nil)
				break;
			// now there may be multiple lines containing the
			// items from l, but the one after the last is lay.end
			l = newline();
			appendline(lay->end->prev, l);
			l->flags |= Lchanged;
			it = nexti;
			l->items = it;
		}
		else
			it = nexti;
	}
}

// Fix up the geometry of line l and successors.
// Assume geometry of previous line is correct.
static void
fixgeom(Frame* f, Lay* lay, Line* l)
{
	while(l != nil) {
		fixlinegeom(f, lay, l);
		l = l->next;
	}
	lay->height = lay->end->pos.y;
}

// Fix geom for one line.
// This may change the overall lay->width, if there is no way
// to fit the line into the target width. 
static void
fixlinegeom(Frame* f, Lay* lay, Line* l)
{
	Line*	lprev;
	int	y;
	Item*	it;
	int	state;
	int	lineh;
	int	lfloatw;
	int	rfloatw;
	int	wrapping;
	int	hang;
	int	linehang;
	int	hangtogo;
	int	indent;
	int	just;
	int	right;
	int	lwid;
	int	w;
	int	linea;
	Item*	lastit;
	List*	nextfloats;
	int	anystuff;
	Item*	rest;
	int	x;
	int	xright;
	int	n;
	int	justw;
	Item*	spaceit;
	int	newlfloatw;
	int	newrfloatw;
	int	kindspec;
	int	avail;
	Ifloat*	ifloat;
	Itable*	itable;
	Irule*	irule;
	Itext*	itext;
	int	oldy;
	int	takeit;
	int	noneok;
	int	iw;
	Line*	nextl;
	Item*	nit;
	int	checkw;
	Item*	qi;
	Item*	li;
	Item*	i;

	lprev = l->prev;
	y = lprev->pos.y + lprev->height;
	it = l->items;
	state = it->state;
	if(dbglay > 1) {
		trace("\nfixlinegeom start, y=prev.y+prev.height=%d+%d=%d, changed=%d\n",
			l->prev->pos.y, lprev->height, y, l->flags&Lchanged);
		if(dbglay > 2)
			printitems(it, "items");
		else
			trace("first item: %I", it);
	}
	if(state&IFbrk) {
		y = pastbrk(lay, y, state);
		if(dbglay > 1 && y != lprev->pos.y + lprev->height)
			trace("after pastbrk, line y is now %d\n", y);
	}
	l->pos.y = y;
	lineh = max(l->height, linespace);
	lfloatw = floatw(y, y + lineh, lay->floats, ALleft);
	rfloatw = floatw(y, y + lineh, lay->floats, ALright);
	if(!(l->flags&Lchanged)) {
		// possibly adjust lay.width
		n = (lay->width - rfloatw) - (l->pos.x - lay->margin + l->width);
		if(n < 0)
			lay->width += -n;
		return ;
	}
	wrapping = state&IFwrap;
	hang = (state&IFhangmask)*TABPIX/10;
	linehang = hang;
	hangtogo = hang;
	indent = ((state&IFindentmask) >> IFindentshift)*TABPIX;
	just = (state&(IFcjust|IFrjust));
	if(just == 0 && lay->just != ALleft) {
		if(lay->just == ALcenter)
			just = IFcjust;
		else if(lay->just == ALright)
			just = IFrjust;
	}
	right = max(lay->targetwidth, lay->width);
	lwid = right - (lfloatw + rfloatw + indent);
	if(lwid < 0) {
		lay->width = lfloatw + rfloatw + indent;
		right = lay->width;
		lwid = 0;
	}
	lwid += hang;
	if(dbglay > 1) {
		trace("fixlinegeom, now y=%d, lfloatw=%d, rfloatw=%d, indent=%d, hang=%d, lwid=%d\n",
				y, lfloatw, rfloatw, indent, hang, lwid);
	}
	l->pos.y = y;
	w = 0;
	lineh = 0;
	linea = 0;
	lastit = nil;
	nextfloats = nil;
	anystuff = 0;
	while(it != nil) {
		if(dbglay > 2)
			trace("fixlinegeom loop head, w=%d, loop item: %I\n", w, it);
		state = it->state;
		if(anystuff && (state&IFbrk))
			break;
		checkw = 1;
		if(hang && !(state&IFhangmask)) {
			lwid -= hang;
			hang = 0;
			if(hangtogo > 0) {
				// insert a null spacer item
				spaceit = newispacer(ISPgeneral);
				spaceit->width = hangtogo;
				if(lastit != nil) {
					spaceit->state = lastit->state&~(IFbrk|IFbrksp|IFnobrk|IFcleft|IFcright);
					lastit->next = spaceit;
				}
				else
					lastit = spaceit;
				spaceit->next = it;
			}
		}
		switch(it->tag) {
		case Ifloattag:
			ifloat = (Ifloat*)it;
			if(anystuff)
				// float will go after this line
				nextfloats = newlist((int)ifloat, nextfloats);
			else {
				// add float beside current line, adjust widths
				fixfloatxy(lay, y, ifloat);
				// TODO: only do following if y and/or height changed
				changelines(l->next, lay->end);
				newlfloatw = floatw(y, y + 1, lay->floats, ALleft);
				newrfloatw = floatw(y, y + 1, lay->floats, ALright);
				lwid -= (newlfloatw - lfloatw) + (newrfloatw - rfloatw);
				if(lwid < 0) {
					lay->width += -lwid;
					right = lay->width;
					lwid = 0;
				}
				lfloatw = newlfloatw;
				rfloatw = newrfloatw;
				if(dbglay > 1)
					trace("float added to current line, i->y=%d, side=%d, h=%d, lfloatw=%d, rfloatw=%d, lwid=%d, lay.width=%d, right=%d\n",
						ifloat->y, ifloat->side, ifloat->item->height,
						lfloatw, rfloatw, lwid, lay->width, right);
			}
			checkw = 0;
			break;
		case Itabletag:
			// When just doing layout for cell dimensions, don't
			// want a "100%" spec to make the table really wide
			itable = (Itable*)it;
			kindspec = 0;
			if(lay->targetwidth == TABLEMAXTARGET && dimenkind(itable->table->width) == Dpercent) {
				kindspec = itable->table->width.kindspec;
				itable->table->width = makedimen(Dnone, 0);
			}
			checktabsize(f, itable, lwid - w);
			if(kindspec != 0)
				itable->table->width.kindspec = kindspec;
			break;
		case Iruletag:
			irule = (Irule*)it;
			avail = lwid - w;
			// When just doing layout for cell dimensions, don't
			// want a "100%" spec to make the rule really wide
			if(lay->targetwidth == TABLEMAXTARGET)
				avail = min(10, avail);
			irule->width = widthfromspec(irule->wspec, avail);
			break;
		case Iformfieldtag:
			checkffsize(f, it, ((Iformfield*)it)->formfield);
			break;
		}
		if(checkw) {
			iw = it->width;
			if(wrapping && w + iw > lwid) {
				// it doesn't fit; see if it can be broken
				// noneok = (anystuff || lfloatw != 0 || rfloatw != 0) && !(state&IFnobrk);
				noneok = anystuff && !(state&IFnobrk);
				takeit = trybreak(it, lwid - w, &iw, noneok);
				if(!takeit) {
					if(lastit == nil) {
						// Nothing added because one of the float widths
						// is nonzero, and not enough room for anything else.
						// Move y down until there's more room and try again.
						assert(lfloatw != 0 || rfloatw != 0);
						oldy = y;
						y = pastbrk(lay, y, IFcleft|IFcright);
						if(dbglay > 1)
							trace("moved y past %d, now y=%d\n", oldy, y);
						assert(y > oldy);
						// Do the move down by artificially increasing the
						// height of the previous line
						lprev->height += y - oldy;
						fixlinegeom(f, lay, l);
						return ;
					}
					break;
				}
			}
			w += iw;
			if(hang)
				hangtogo -= w;
			updatelgeom(&lineh, &linea, it);
			if(!anystuff) {
				anystuff = 1;
				// don't count an ordinary space as 'stuff' if wrapping
				if(it->tag == Itexttag && wrapping && ((Itext*)it)->s[0] == ' ')
					anystuff = 0;
			}
		}
		lastit = it;
		it = it->next;
		if(it == nil) {
			// perhaps next lines items can now fit on this line
			nextl = l->next;
			nit = nextl->items;
			if(nextl != lay->end && !(nit->state&IFbrk)) {
				lastit->next = nit;
				// remove nextl
				l->next = nextl->next;
				l->next->prev = l;
				it = nit;
			}
		}
	}
	// line is complete, next line will start with it (or it is nil)
	rest = it;
	assert(lastit != nil);
	lastit->next = nil;
	l->width = w;
	x = lfloatw + indent - linehang;
	i = l->items;
	switch(i->tag) {
	case Itexttag:
		itext = (Itext*)i;
		if(itext->s[0] == ' ')
			x -= fonts[itext->fnt].spw;
		break;
	case Iruletag:
		irule = (Irule*)i;
		if(irule->align == ALcenter)
			just = IFcjust;
		else if(irule->align == ALright)
			just = IFrjust;
		break;
	case Ifloattag:
		ifloat = (Ifloat*)i;
		if(ifloat->next != nil) {
			qi = ifloat->next;
			if(qi->tag == Itexttag) {
				itext = (Itext*)qi;
				if(itext->s[0] == ' ')
					x -= fonts[itext->fnt].spw;
			}
		}
		break;
	}
	xright = x + w;
	n = (lay->width - rfloatw) - xright;
	if(n < 0) {
		lay->width += -n;
	}

	// except when doing the maximum needed cell width, justification
	// is supposed to be within max(lay.width, targetwidth),
	// but also, if this is lay for frame itself, justify within f.targetwidth to match other browsers.
	if(lay == f->layout)
		justw = lay->targetwidth;
	else if(lay->targetwidth == TABLEMAXTARGET)
		justw = lay->width;
	else
		justw = max(lay->width, lay->targetwidth);
	n = (justw - rfloatw) - xright;
	if(n > 0 && just) {
		if(just&IFcjust)
			x += n/2;
		else
			x += n;
		if(x + w + rfloatw > lay->width)
			lay->width = x + w + rfloatw;
	}
	if(dbglay > 1) {
		trace("line geometry fixed, (x,y)=(%d,%d), w=%d, h=%d, a=%d, lfloatw=%d, rfloatw=%d, lay.width=%d\n",
			x, l->pos.y, w, lineh, linea, lfloatw, rfloatw, lay->width);
		if(dbglay > 2)
			printitems(l->items, "final line items");
	}
	l->pos.x = x + lay->margin;
	l->height = lineh;
	l->ascent = linea;
	l->flags &= ~Lchanged;
	if(nextfloats != nil)
		fixfloatsafter(lay, l, nextfloats);
	if(rest != nil) {
		nextl = l->next;
		if(nextl == lay->end || (nextl->items->state&IFbrk)) {
			nextl = newline();
			appendline(l, nextl);
		}
		li = lastitem(rest);
		li->next = nextl->items;
		nextl->items = rest;
		nextl->flags |= Lchanged;
	}
}

// Return y coord after y due to a break.
static int
pastbrk(Lay* lay, int y, int state)
{
	int	nextralines;
	int	ynext;

	nextralines = 0;
	if(state&IFbrksp)
		nextralines = 1;
	ynext = y;
	if(state&IFcleft)
		ynext = floatclry(lay->floats, ALleft, ynext);
	if(state&IFcright)
		ynext = max(ynext, floatclry(lay->floats, ALright, ynext));
	ynext += nextralines*linespace;
	return ynext;
}

// Add line l after lprev (and before lprev's current successor)
static void
appendline(Line* lprev, Line* l)
{
	l->next = lprev->next;
	l->prev = lprev;
	l->next->prev = l;
	lprev->next = l;
}

// Mark lines l up to but not including lend as changed
static void
changelines(Line* l, Line* lend)
{
	for(; l != lend; l = l->next)
		l->flags |= Lchanged;
}

// Return a Font* for font number num = (style*NumSize + size)
static Font*
getfont(int num)
{
	Font*	f;

	f = fonts[num].f;
	if(f == nil) {
		f = openfont(display, fonts[num].name);
		if(f == nil) {
			if(num == DefFnt) {
				trace("can't open default font\n");
assert(0);
				exits("font problem");
			}
			else {
				if(warn)
					trace("warning: substituting default for font %s\n", fonts[num].name);
				f = fonts[DefFnt].f;
			}
		}
		fonts[num].f = f;
		fonts[num].spw = runestringwidth(f, L" ");
	}
	return f;
}

// Set the width, height and ascent fields of all items, getting any necessary fonts.
// Some widths and heights depend on the available width on the line, and may be
// wrong until checked during fixlinegeom.
// Don't do tables here at all (except floating tables).
// Configure Controls for form fields.
static void
measure(Frame* fr, Item* items)
{
	Item*	it;
	Font*	f;
	int	a;
	int	h;
	Control*	c;
	Item*	i;
	Itext*	t;
	Irule*	r;
	Iformfield*	ff;
	Ifloat*	fl;

	for(it = items; it != nil; it = it->next) {
		switch(it->tag) {
		case Itexttag:
			t = (Itext*)it;
			f = getfont(t->fnt);
			it->width = runestringwidth(f, t->s);
			a = f->ascent;
			h = f->height;
			if(t->voff != Voffbias) {
				a -= (t->voff) - Voffbias;
				if(a > h)
					h = a;
			}
			it->height = h;
			it->ascent = a;
			break;
		case Iruletag:
			r = (Irule*)it;
			it->height = r->size + 2*RULESP;
			it->ascent = r->size + RULESP;
			break;
		case Iimagetag:
			setimagedims((Iimage*)it);
			break;
		case Iformfieldtag:
			ff = (Iformfield*)it;
			c = newff(fr, ff->formfield);
			if(c != nil) {
				ff->formfield->ctlid = addcontrol(fr, c);
				it->width = Dx(c->r);
				it->height = Dy(c->r);
				it->ascent = it->height;
				switch(c->tag) {
				case Centrytag:
					it->ascent = lineascent + ENTVMARGIN;
					break;
				case Cselecttag:
					it->ascent = lineascent + SELMARGIN;
					break;
				case Cbuttontag:
					if(((Cbutton*)c)->dorelief)
						it->ascent -= BUTMARGIN;
					break;
				}
			}
			break;
		case Ifloattag:
			// Leave w at zero, so it doesn't contribute to line width in normal way
			// (Can find its width in t.item.width).
			fl = (Ifloat*)it;
			i = fl->item;
			switch(i->tag) {
			case Iimagetag:
				setimagedims((Iimage*)i);
				it->height = i->height;
				break;
			case Itabletag:
				checktabsize(fr,(Itable*)i, TABLEFLOATTARGET);
				break;
			default:
				assert(0);
				break;
			}
			it->ascent = it->height;
			break;
		case Ispacertag:
			switch(((Ispacer*)it)->spkind) {
			case ISPvline:
				it->height = linespace;
				it->ascent = lineascent;
				break;
			case ISPhspace:
				it->width = spspace;
				break;
			}
			break;
		}
	}
}

// Set the dimensions of an image item
static void
setimagedims(Iimage* i)
{
	Font*	f;

	i->width = i->imwidth + 2*(i->hspace + i->border);
	i->height = i->imheight + 2*(i->vspace + i->border);
	i->ascent = i->height - (i->vspace + i->border);
	if(config.imagelvl == ImgNone && i->altrep != nil) {
		f = fonts[DefFnt].f;
		i->width = max(i->width, runestringwidth(f, i->altrep));
		i->height = max(i->height, f->height);
		i->ascent = f->ascent;
	}
}

// Line geometry function:
// Given current line height (*pH) and ascent (distance from top to baseline) (*pA),
// and an item, see if that item changes height and ascent.
// Return (H', A') in *pH and *pA, the updated line height and ascent.
static void
updatelgeom(int* pH, int* pA, Item* it)
{
	int	h;
	int	a;
	uchar	atype;
	int	d;
	int	Hnew;
	int	Anew;
	int	hhalf;
	int	H;
	int	A;

	H = *pH;
	A = *pA;
	h = it->height;
	a = it->ascent;
	atype = ALbaseline;
	switch(it->tag) {
	case Iimagetag:
		atype = ((Iimage*)it)->align;
		break;
	case Itabletag:
		atype = ALtop;
		break;
	case Ifloattag:
		return;
	}
	d = h - a;
	Hnew = H;
	Anew = A;
	switch(atype) {
	case ALbaseline:
	case ALbottom:
		if(a > A) {
			Anew = a;
			Hnew += (Anew - A);
		}
		if(d > Hnew - Anew)
			Hnew = Anew + d;
		break;
	case ALtop:
		if(h > H)
			Hnew = h;
		break;
	case ALmiddle:
	case ALcenter:
		hhalf = h/2;
		if(hhalf > A)
			Anew = hhalf;
		if(hhalf > H - Anew)
			Hnew = Anew + hhalf;
		break;
	}
	*pH = Hnew;
	*pA = Anew;
}

// Try breaking item bit to make it fit in availw.
// If that is possible, change bit to be the part that fits
// and insert the rest between bit and bit.next.
// *piw is the current width of bit.
// If noneok is 0, break off the minimum size word
// even if it exceeds availw.
// Return 1 if supposed to take bit, and iw' = new width of bit in *piw
static int
trybreak(Item* bit, int availw, int* piw, int noneok)
{
	Item*	itn;
	Itext*	t;
	int		iw;
	Rune*	s1;
	Rune*	s2;
	int		w1;
	int		w2;

	iw = *piw;
	if(iw <= 0)
		return 1;
	if(availw < 0) {
		if(noneok)
			return 0;
		else
			availw = 0;
	}
	if(bit->tag == Itexttag) {
		t = (Itext*)bit;
		assert(t->s != nil);
		if(breakstring(t->s, iw, fonts[t->fnt].f, availw, noneok, &s1, &w1, &s2, &w2) < 0)
			return !noneok;
		if(w1 == 0)
			return 0;
		// here we split bit into two pieces at i
		assert(s1 != nil && s2 != nil);
		itn = newitext(s2, t->fnt, t->fg, t->voff, t->ul);
		itn->width = w2;
		itn->height = t->height;
		itn->ascent = t->ascent;
		itn->anchorid = t->anchorid;
		itn->state = t->state&~(IFbrk|IFbrksp|IFnobrk|IFcleft|IFcright);
		itn->next = t->next;
		t->next = itn;
		t->s = s1;
		t->width = w1;
		*piw = w1;
		return 1;
	}
	return !noneok;
}

// s has width sw when drawn in fnt.
// Break s into s1 and s2 so that s1 fits in availw.
// If noneok is true, it is ok for s1 to be nil, otherwise might
// have to return an s1 that overflows availw somewhat.
// Return vals in *ps1, *pw1, *ps2, *pw2 where w1 and w2
// are widths of s1 and s2.
// Also, return -1 if no break is possible within s,
// so the caller needs to take all or nothing.
// Assume caller has already checked that sw > availw.
static int
breakstring(Rune* s, int sw, Font* fnt, int availw, int noneok,
	Rune** ps1, int* pw1, Rune** ps2, int* pw2)
{
	int slen;
	int i;
	int oldi;
	int ww;
	int oldww;
	Rune* ss;
	Rune* oldss;

	slen = Strlen(s);
	if(slen < 2)
		return -1;
	// Use linear interpolation to guess break point.
	// We know avail < iw by conditions of trybreak call.
	i = slen*availw/sw - 1;
	if(i < 0)
		i = 0;
	i = breakpoint(s, slen, i, -1);
	ww = tryw(fnt, s, i, &ss);
	if(ww > availw) {
		while(ww > availw) {
			i = breakpoint(s, slen, i - 1, -1);
			if(i <= 0)
				break;
			ww = tryw(fnt, s, i, &ss);
		}
	}
	else {
		oldi = i;
		oldss = ss;
		oldww = ww;
		while(ww < availw) {
			oldi = i;
			oldss = ss;
			oldww = ww;
			i = breakpoint(s, slen, i + 1, 1);
			if(i >= slen)
				break;
			ww = tryw(fnt, s, i, &ss);
		}
		i = oldi;
		ss = oldss;
		ww = oldww;
	}
	if(i <= 0 || i >= slen) {
		if(noneok) {
			*ps1 = nil;
			*pw1 = 0;
			*ps2 = s;
			*pw2 = sw;
			return 0;
		}
		i = breakpoint(s, slen, 1, 1);
		if(i >= slen)
			return -1;
		ww = tryw(fnt, s, i, &ss);
	}
	*ps1 = ss;
	*pw1 = ww;
	*ps2 = Strndup(s+i, slen-i);
	*pw2 = sw-ww;
	return 1;
}

// If can break between s[i-1] and s[i], return i.
// Else move i in direction incr until this is true.
// (Might end up returning 0 or len s).
static int
breakpoint(Rune* s, int slen, int i, int incr)
{
	int	ans;
	int	ci;
	int	di;

	ans = 0;
	while(i > 0 && i < slen) {
		ci = s[i];
		di = s[i - 1];
		if((ci >= 0xA0 || wordchar[ci]) && (di >= 0xA0 || wordchar[di]))
			i += incr;
		else {
			ans = i;
			break;
		}
	}
	if(i == slen)
		ans = slen;
	return ans;
}

// Return (s[0:i], width of that slice in font fnt)
static int
tryw(Font* fnt, Rune* s, int i, Rune** pss)
{
	if(i == 0) {
		*pss = nil;
		return 0;
	}
	*pss = Strndup(s, i);
	return runestringwidth(fnt, *pss);
}

// Return max width of a float that overlaps [ymin, ymax) on given side.
// Floats are in reverse order of addition, so each float's y is <= that of
// preceding floats in list.  Floats from both sides are intermixed.
static int
floatw(int ymin, int ymax, Ifloat* flist, uchar side)
{
	int	ans;
	int	w;
	Ifloat*	fl;
	int	fymin;
	int	fymax;

	ans = 0;
	for(fl = flist; fl != nil; fl = fl->nextfloat) {
		if(fl->side != side)
			continue;
		fymin = fl->y;
		fymax = fymin + fl->item->height;
		if((fymin <= ymin && ymin < fymax) || (ymin <= fymin && fymin < ymax)) {
			w = fl->x;
			if(side == ALleft)
				w += fl->item->width;
			if(ans < w)
				ans = w;
		}
	}
	return ans;
}

// Float f is to be at vertical position >= y.
// Fix its (x,y) pos and add it to lay.floats, if not already there.
static void
fixfloatxy(Lay* lay, int y, Ifloat* f)
{
	Ifloat*	flist;
	Ifloat*	x;

	f->y = y;
	flist = lay->floats;
	if(!f->infloats) {
		// only take previous floats into account for width
		while(flist != nil) {
			x = flist;
			flist = flist->nextfloat;
			if(x == f)
				break;
		}
	}
	f->x = floatw(y, y + f->item->height, flist, f->side);
	// for right-side floats, x is distance from right edge,
	// which includes f's width
	if(f->side == ALright)
		f->x += f->item->width;
	if(dbglay > 1)
		trace("fixfloatxy, now float is: %I\n", (Item*)f);
	if(!f->infloats) {
		f->nextfloat = lay->floats;
		lay->floats = f;
		f->infloats = 1;
	}
}

// Floats in flist are to go after line l.
static void
fixfloatsafter(Lay* lay, Line* l, List* flist)
{
	int	y;
	List*	itl;
	Ifloat*	ifloat;

	y = l->pos.y + l->height;
	for(itl = revlist(flist); flist != nil; flist = flist->next) {
		ifloat = (Ifloat*)(itl->val);
		assert(ifloat->tag == Ifloattag);
		fixfloatxy(lay, y, ifloat);
	}
	// TODO: only change if y and/or height changed
	changelines(l->next, lay->end);
}

// If there's a float on given side that starts on or before y and
// ends after y, return ending y of that float, else return original y.
// Assume float list is bottom up.
static int
floatclry(Ifloat* fl, uchar side, int y)
{
	int	flymax;

	for(; fl != nil; fl = fl->nextfloat) {
		if(fl->side == side) {
			if(fl->y <= y) {
				flymax = fl->y + fl->item->height;
				if(flymax <= y)
					return y;
				else
					return flymax;
			}
		}
	}
	return y;
}

// Do preliminaries to laying out table tab in target width linewidth,
// setting total height and width.
static void
sizetable(Frame* f, Table* tab, int availwidth)
{
	int	hsp;
	int	vsp;
	int	pad;
	int	bd;
	int	cbd;
	int	hsep;
	int	vsep;
	int	totw;
	int*	colmaxw;
	int	maxw;
	int	ci;
	int	ri;
	int	toth;
	int	tw;
	Tablecell*	c;
	Lay*	clay;
	int	d;
	int	wd;
	int*	colminw;
	int	minw;
	int	w;
	uchar	al;
	Tablerow*	row;
	int	h;
	int	a;
	int	n;
	int	spanht;
	int	i;
	int	ht;
	Lay*	caplay;

	if(dbgtab)
		trace("sizetable %d, availwidth=%d, nrow=%d, ncol=%d, changed=%x, tab.availw=%d\n",
			tab->tableid, availwidth, tab->nrow, tab->ncol, tab->flags&Lchanged, tab->availw);
	if(tab->ncol == 0 || tab->nrow == 0)
		return ;
	if(tab->availw == availwidth && !(tab->flags&Lchanged))
		return ;
	tableparams(tab, &hsp, &vsp, &pad, &bd, &cbd, &hsep, &vsep);
	totw = widthfromspec(tab->width, availwidth);
	// reduce totw by spacing, padding, and rule widths
	// to leave amount left for contents
	totw -= (tab->ncol - 1)*hsep + 2*(hsp + bd + pad + cbd);

	if(totw <= 0)
		totw = 1;
	if(dbgtab)
		trace("\nsizetable %d, totw=%d, hsp=%d, vsp=%d, pad=%d, bd=%d, cbd=%d, hsep=%d, vsep=%d\n",
			tab->tableid, totw, hsp, vsp, pad, bd, cbd, hsep, vsep);
	for(c = tab->cells; c != nil; c = c->next) {
		clay = c->lay;
		if(clay == nil || !(clay->flags&Lchanged)) {
			c->minw = -1;
			tw = TABLEMAXTARGET;
			if(dimenkind(c->wspec) != Dnone)
				tw = widthfromspec(c->wspec, totw);

			// When finding max widths, want to lay out using ALleft alignment,
			// because we don't yet know final width for proper justification.
			// If the max widths are accepted, we'll redo those needing other justification.
			if(clay == nil) {
				if(dbglay)
					trace("Initial layout for cell %d.%d\n", tab->tableid, c->cellid);
				clay = c->lay = sublayout(f, tw, ALleft, c->background, c->content);
				c->content = nil;
			}
			else {
				if(dbglay)
					trace("Relayout (for max) for cell %d.%d\n", tab->tableid, c->cellid);
				relayout(f, clay, tw, ALleft);
			}
			clay->flags |= Lchanged;	// for min test, below
			c->maxw = clay->width;
			if(dbgtab)
				trace("sizetable %d for cell %d max layout done, targw=%d, c.maxw=%d\n",
					tab->tableid, c->cellid, tw, c->maxw);
			if(dimenkind(c->wspec) == Dpixels) {
				// Other browsers don't make the following adjustment for
				// percentage and relative widths
				if(c->maxw <= tw)
					c->maxw = tw;
				if(dbgtab)
					trace("after spec adjustment, c.maxw=%d\n", c->maxw);
			}
		}
	}

	// calc max column widths
	colmaxw = (int*)emallocz(tab->ncol * sizeof(int));
	maxw = widthcalc(tab, colmaxw, hsep, 1);
	if(dbgtab)
		trace("sizetable %d maxw=%d, totw=%d\n", tab->tableid, maxw, totw);
	if(maxw <= totw) {
		// trial layouts are fine,
		// but if table width was specified, add more space
		d = 0;
		if(totw > maxw && dimenkind(tab->width) != Dnone)
			d = (totw - maxw)/tab->ncol;
		for(ci = 0; ci < tab->ncol; ci++) {
			tab->cols[ci].width = colmaxw[ci] + d;
			if(dbgtab)
				trace("sizetable %d tab.cols[%d].width = %d\n", tab->tableid, ci, colmaxw[ci]);
		}
	}
	else {
		// calc min column widths and  apportion out
		// differences
		if(dbgtab)
			trace("sizetable %d, availwidth %d, need min widths too\n", tab->tableid, availwidth);
		for(c = tab->cells; c != nil; c = c->next) {
			clay = c->lay;
			assert(clay != nil);
			if(c->minw == -1 || !(clay->flags&Lchanged)) {
				if(dbglay)
					trace("Relayout (for min) for cell %d.%d\n", tab->tableid, c->cellid);
				relayout(f, clay, 1, ALleft);
				c->minw = clay->width;
				if(dbgtab)
					trace("sizetable %d for cell %d min layout done, c.min=%d\n",
						tab->tableid, c->cellid, clay->width);
			}
		}
		colminw = (int*)emallocz(tab->ncol * sizeof(int));
		minw = widthcalc(tab, colminw, hsep, 0);
		w = totw - minw;
		d = maxw - minw;
		if(dbgtab)
			trace("sizetable %d minw=%d, w=%d, d=%d\n", tab->tableid, minw, w, d);
		for(ci = 0; ci < tab->ncol; ci++) {
			if(w < 0 || d < 0)
				wd = colminw[ci];
			else
				wd = colminw[ci] + (colmaxw[ci] - colminw[ci])*w/d;
			if(dbgtab)
				trace("sizetable %d col[%d].width = %d\n", tab->tableid, ci, wd);
			tab->cols[ci].width = wd;
		}
		if(dbgtab)
			trace("sizetable %d, availwidth %d, doing final layouts\n", tab->tableid, availwidth);
	}

	// now have col widths; set actual cell dimensions
	// and relayout (note: relayout will do no work if the target width
	// and just haven't changed from last layout)
	for(c = tab->cells; c != nil; c = c->next) {
		clay = c->lay;
		wd = cellwidth(tab, c, hsep);
		if(dbgtab)
			trace("sizetable %d for cell %d, clay.width=%d, cellwidth=%d\n",
				tab->tableid, c->cellid, clay->width, wd);
		if(dbglay)
			trace("Relayout (final) for cell %d.%d\n", tab->tableid, c->cellid);
		relayout(f, clay, wd, c->align.halign);
		if(dbgtab)
			trace("sizetable %d for cell %d, final width %d, got width %d, height %d\n",
				tab->tableid, c->cellid, wd, clay->width, clay->height);
	}

	// set row heights and ascents
	// first pass: ignore cells with rowspan > 1
	for(ri = 0; ri < tab->nrow; ri++) {
		row = &tab->rows[ri];
		h = 0;
		a = 0;
		for(c = row->cells; c != nil; c = c->nextinrow) {
			clay = c->lay;
			if(c->rowspan > 1 || clay == nil)
				continue;
			al = c->align.valign;
			if(al == ALnone)
				al = tab->rows[c->row].align.valign;
			if(al == ALbaseline) {
				n = c->ascent;
				if(n > a) {
					h += (n - a);
					a = n;
				}
				n = clay->height - c->ascent;
				if(n > h - a)
					h = a + n;
			}
			else {
				n = clay->height;
				if(n > h)
					h = n;
			}
		}
		row->height = h;
		row->ascent = a;
	}
	// second pass: take care of rowspan > 1
	// (this algorithm isn't quite right -- it might add more space
	// than is needed in the presence of multiple overlapping rowspans)
	for(c = tab->cells; c != nil; c = c->next) {
		if(c->rowspan > 1) {
			spanht = 0;
			for(i = 0; i < c->rowspan && c->row + i < tab->nrow; i++)
				spanht += tab->rows[c->row + i].height;
			clay = c->lay;
			if(clay == nil)
				continue;
			ht = clay->height - (c->rowspan - 1)*vsep;
			if(ht > spanht) {
				// add extra space to last spanned row
				i = c->row + c->rowspan - 1;
				if(i >= tab->nrow)
					i = tab->nrow - 1;
				tab->rows[i].height += ht - spanht;
				if(dbgtab)
					trace("sizetable %d, row %d height %d\n",
						tab->tableid, i, tab->rows[i].height);
			}
		}
	}
	// get total width, heights, and col x / row y positions
	totw = bd + hsp + cbd + pad;
	for(ci = 0; ci < tab->ncol; ci++) {
		tab->cols[ci].pos.x = totw;
		if(dbgtab)
			trace("sizetable %d, col %d at x=%d\n", tab->tableid, ci, totw);
		totw += tab->cols[ci].width + hsep;
	}
	totw = totw - (cbd + pad) + bd;
	toth = bd + vsp + cbd + pad;
	// first time: move tab.caption items into layout
	if(tab->caption != nil) {
		// lay caption with ALleft; drawing will center it over the table width
		tab->caption_lay = sublayout(f, availwidth, ALleft, f->layout->background, tab->caption);
		caplay = tab->caption_lay;
		tab->caph = caplay->height + CAPSEP;
		tab->caption = nil;
	}
	else if(tab->caption_lay != nil) {
		caplay = tab->caption_lay;
		if(tab->availw != availwidth || (caplay->flags&Lchanged) != (uchar)0) {
			relayout(f, caplay, availwidth, ALleft);
			tab->caph = caplay->height + CAPSEP;
		}
	}
	if(tab->caption_place == ALtop)
		toth += tab->caph;
	for(ri = 0; ri < tab->nrow; ri++) {
		tab->rows[ri].pos.y = toth;
		if(dbgtab)
			trace("sizetable %d, row %d at y=%d\n", tab->tableid, ri, toth);
		toth += tab->rows[ri].height + vsep;
	}
	toth = toth - (cbd + pad) + bd;
	if(tab->caption_place == ALbottom)
		toth += tab->caph;
	tab->totw = totw;
	tab->toth = toth;
	tab->availw = availwidth;
	tab->flags &= ~Lchanged;
	if(dbgtab)
		trace("\ndone sizetable %d, availwidth %d, totw=%d, toth=%d\n\n",
			tab->tableid, availwidth, totw, toth);
}

// Calculate various table spacing parameters
static void
tableparams(Table* tab, int* hsp, int* vsp, int* pad, int* bd, int* cbd, int* hsep, int* vsep)
{
	*bd = tab->border;
	*hsp = tab->cellspacing;
	*vsp = *hsp;
	*pad = tab->cellpadding;
	*cbd = (tab->border)? 1 : 0;
	*hsep = 2*(*cbd + *pad) + *hsp;
	*vsep = 2*(*cbd + *pad) + *vsp;
}

// return cell width, taking multicol spanning into account
static int
cellwidth(Table* tab, Tablecell* c, int hsep)
{
	int	wd;
	int	i;

	if(c->colspan == 1)
		return tab->cols[c->col].width;
	wd = (c->colspan - 1)*hsep;
	for(i = 0; i < c->colspan && c->col + i < tab->ncol; i++)
		wd += tab->cols[c->col + i].width;
	return wd;
}

// return cell height, taking multirow spanning into account
static int
cellheight(Table* tab, Tablecell* c, int vsep)
{
	int	ht;
	int	i;

	if(c->rowspan == 1)
		return tab->rows[c->row].height;
	ht = (c->rowspan - 1)*vsep;
	for(i = 0; i < c->rowspan && c->row + i < tab->nrow; i++)
		ht += tab->rows[c->row + i].height;
	return ht;
}

// Calculate the column widths w as the max of the cells
// maxw or minw (as domax is 1 or 0).
// Return the total of all w.
// (hseps were accounted for by the adjustment that got
// totw from availwidth).
// hsep is amount of free space available between columns
// where there is multicolumn spanning.
// This is a two-pass algorithm.  The first pass ignores
// cells that span multiple columns.  The second pass
// sees if those multispanners need still more space, and
// if so, apportions the space out.
static int
widthcalc(Table* tab, int* w, int hsep, int domax)
{
	int	anyspan;
	int	totw;
	int	pass;
	int	curw;
	int	iend;
	int	i;
	int	diff;
	Tablecell*	c;
	int	cwd;
	int	ri;
	int	ci;

	anyspan = 0;
	totw = 0;
	for(pass = 1; pass <= 2; pass++) {
		if(pass == 2 && !anyspan)
			break;
		totw = 0;
		for(ci = 0; ci < tab->ncol; ci++) {
			for(ri = 0; ri < tab->nrow; ri++) {
				c = tab->grid[ri][ci];
				if(c == nil)
					continue;
				cwd = domax? c->maxw : c->minw;
				if(pass == 1) {
					if(c->colspan > 1) {
						anyspan = 1;
						continue;
					}
					if(cwd > w[ci])
						w[ci] = cwd;
				}
				else {
					if(c->colspan == 1 || !(ci == c->col && ri == c->row))
						continue;
					curw = 0;
					iend = ci + c->colspan;
					if(iend > tab->ncol)
						iend = tab->ncol;
					for(i = ci; i < iend; i++)
						curw += w[i];
				
					// padding between spanned cols is free
					cwd -= hsep*(c->colspan - 1);
					diff = cwd - curw;
					if(diff <= 0)
						continue;
					for(i = ci; i < iend; i++) {
						if(curw == 0)
							w[i] = diff/c->colspan;
						else
							w[i] += diff*w[i]/curw;
					}
				}
			}
			totw += w[ci];
		}
	}
	return totw;
}

static void
layframeset(Frame* f, Kidinfo* ki)
{
	int	fwid;
	int	fht;
	int	nrow;
	int*	rowh;
	int	ncol;
	int*	colw;
	Kidinfo*	l;
	int	y;
	int	i;
	Framelist*	al;
	Rectangle	r;
	Kidinfo*	kidki;
	Frame*	kidf;
	int	x;
	int	j;

	fwid = Dx(f->cr);
	fht = Dy(f->cr);
	if(dbglay)
		trace("layframeset, configuring frame %d wide by %d high\n", fwid, fht);
	nrow = frdimens(ki->rows, ki->nrows, fht, &rowh);
	ncol = frdimens(ki->cols, ki->ncols, fwid, &colw);
	l = ki->kidinfos;
	y = f->cr.min.y;
	for(i = 0; i < nrow; i++) {
		x = f->cr.min.x;
		for(j = 0; j < ncol; j++) {
			if(l == nil)
				return;
			r = Rect(x, y, x + colw[j], y + rowh[i]);
			if(dbglay)
				trace("kid gets rect (%d,%d)(%d,%d)\n", r.min.x, r.min.y, r.max.x, r.max.y);
			kidki = l;
			l = l->next;
			kidf = newkid(f, kidki, r);
			if(!kidki->isframeset)
				f->kids = newframelist(kidf, f->kids);
			if(kidf->framebd != 0) {
				kidf->cr = insetrect(kidf->r, 2);
				drawborder(kidf->cim, kidf->cr, 2, DarkGrey);
			}
			if(kidki->isframeset) {
				layframeset(kidf, kidki);
				for(al = kidf->kids; al != nil; al = al->next)
					f->kids = newframelist(al->val, f->kids);
			}
			x += colw[j];
		}
		y += rowh[i];
	}
}

// Use the dimension specs in dims to allocate total space t.
// Return number of dimens, and put an array of allocated space in *parr.
static int
frdimens(Dimen* dims, int n, int t, int** parr)
{
	int	totpix;
	int	totpcnt;
	int	totrel;
	int	i;
	double	spix;
	double	spcnt;
	int	min_relu;
	double	relu;
	int	tt;
	int*	x;
	int	v;
	int	kind;
	int	trest;
	int	totpixrel;
	double	vr;

	if(n == 1) {
		*parr = x = (int*)emalloc(sizeof(int));
		x[0] = t;
		return 1;
	}
	totpix = 0;
	totpcnt = 0;
	totrel = 0;
	for(i = 0; i < n; i++) {
		v = dimenspec(dims[i]);
		kind = dimenkind(dims[i]);
		if(v < 0) {
			v = 0;
			dims[i] = makedimen(kind, v);
		}
		switch(kind) {
		case Dpixels:
			totpix += v;
			break;
		case Dpercent:
			totpcnt += v;
			break;
		case Drelative:
			totrel += v;
			break;
		case Dnone:
			totrel++;
			break;
		}
	}
	spix = 1.0;
	spcnt = 1.0;
	min_relu = 0;
	if(totrel > 0)
		min_relu = 30;	// allow for scrollbar (14) and a bit
	relu = (double)min_relu;
	tt = totpix + (t*totpcnt/100) + totrel*min_relu;
	// want
	//  t ==  totpix*spix + (totpcnt/100)*spcnt*t + totrel*relu
	if(tt < t) {
		if(totrel == 0) {
			if(totpcnt != 0)
				// spix==1.0, relu==0, solve for spcnt
				spcnt = (double)((t - totpix)*100)/(double)(t*totpcnt);
			else
				// relu==0, totpcnt==0, solve for spix
				spix = (double)t/(double)totpix;
		}
		else
			// spix=1.0, spcnt=1.0, solve for relu
			relu += (double)(t - tt)/(double)totrel;
	}
	else {
		// need to contract one or more of spix, spcnt, and have relu==min_relu
		totpixrel = totpix + totrel*min_relu;
		if(totpixrel < t) {
			// spix==1.0, solve for spcnt
			spcnt = (double)((t - totpixrel)*100)/(double)(t*totpcnt);
		}
		else {
			// let spix==spcnt, solve
			trest = t - totrel*min_relu;
			if(trest > 0) {
				spcnt = (double)trest/(double)(totpix + (t*totpcnt/100));
			}
			else {
				spcnt = (double)t/(double)tt;
				relu = 0.0;
			}
			spix = spcnt;
		}
	}
	x = (int*)emalloc(n * sizeof(int));
	tt = 0;
	for(i = 0; i < n - 1; i++) {
		vr = (double)dimenspec(dims[i]);
		switch(dimenkind(dims[i])) {
		case Dpixels:
			vr = vr*spix;
			break;
		case Dpercent:
			vr = vr*(double)t*spcnt/100.0;
			break;
		case Drelative:
			vr = vr*relu;
			break;
		case Dnone:
			vr = relu;
			break;
		}
		x[i] = (int)(vr+.5);
		tt += x[i];
	}
	x[n - 1] = t - tt;
	*parr = x;
	return n;
}

// Return last item of list of items, or nil if no items
static Item*
lastitem(Item* it)
{
	Item*	ans;

	ans = it;
	for(; it != nil; it = it->next)
		ans = it;
	return ans;
}

// Lay out table if availw changed or tab changed
static void
checktabsize(Frame* f, Itable* t, int availw)
{
	Table*	tab;

	tab = t->table;
	if(availw != tab->availw || (tab->flags&Lchanged)) {
		sizetable(f, tab, availw);
		t->width = tab->totw + 2*tab->border;
		t->height = tab->toth + 2*tab->border;
		t->ascent = t->height;
	}
}

static int
widthfromspec(Dimen wspec, int availw)
{
	int	w;
	int	spec;

	w = availw;
	spec = dimenspec(wspec);
	switch(dimenkind(wspec)) {
	case Dpixels:
		w = spec;
		break;
	case Dpercent:
		w = spec*w/100;
		break;
	}
	return w;
}

// An image may have arrived for an image input field
static void
checkffsize(Frame* f, Item* i, Formfield* ff)
{
	int	w;
	int	h;
	Control*	c;
	Cbutton*	b;
	Iimage*	imi;

	if(ff->ftype == Fimage) {
		assert(ff->image->tag == Iimagetag);
		imi = (Iimage*)ff->image;
		if(imi->ci->mims != nil && ff->ctlid >= 0) {
			c = f->controls[ff->ctlid];
			if(c->tag == Cbuttontag) {
				b = (Cbutton*)c;
				if(b->pic == nil) {
					b->pic = imi->ci->mims[0]->im;
					b->picmask = imi->ci->mims[0]->mask;
					w = Dx(b->pic->r);
					h = Dy(b->pic->r);
					b->r.max.x = b->r.min.x + w;
					b->r.max.y = b->r.min.y + h;
					i->width = w;
					i->height = h;
					i->ascent = h;
				}
			}
		}
	}
}

static void
drawall(Frame* f)
{
	Point	origin;

	pushclipr(f->cr);
	fillbg(f, f->cr);
	origin = lptosp(f, Pt(0, 0));
	if(dbglay > 1)
		trace("drawall, cr=(%d,%d,%d,%d), viewr=(%d,%d,%d,%d), origin=(%d,%d)\n",
			f->cr.min.x, f->cr.min.y, f->cr.max.x, f->cr.max.y,
			f->viewr.min.x, f->viewr.min.y, f->viewr.max.x, f->viewr.max.y,
			origin.x, origin.y);
	if(f->layout != nil)
		drawlay(f, f->layout, origin);
	popclipr();
	flushc(f);
}

static void
drawlay(Frame* f, Lay* lay, Point origin)
{
	Line*	l;

	for(l = lay->start->next; l != lay->end; l = l->next)
		drawline(f, origin, l, lay);
}

// Draw line l in frame f, assuming that content's (0,0)
// aligns with layorigin in f->cim.
static void
drawline(Frame* f, Point layorigin, Line* l, Lay* lay)
{
	Image*	im;
	Point	o;
	int	x;
	int	y;
	Item*	it;
	Font*	fnt;
	int	yy;
	Image*	fgi;
	Control*	ctl;
	Point	dims;
	Point	p;
	Formfield*	ff;
	int	xx;
	Itext*	i;
	Irule*	ir;
	Iimage*	ii;
	Ifloat*	ifl;

	im = f->cim;
	o = addpt(layorigin, l->pos);
	x = o.x;
	y = o.y;
	for(it = l->items; it != nil; it = it->next) {
		switch(it->tag) {
		case Itexttag:
			i = (Itext*)it;
			fnt = fonts[i->fnt].f;
			yy = y + l->ascent - fnt->ascent + (i->voff) - Voffbias;
			fgi = colorimage(i->fg);
			runestring(im, Pt(x, yy), fgi, ZP, fnt, i->s);
			if(i->ul != ULnone) {
				if(i->ul == ULmid)
					yy += 2*i->ascent/3;
				else
					yy += i->height - 1;
				draw(im, Rect(x, yy, x + i->width, yy + 1), fgi, nil, ZP);
			}
			break;
		case Iruletag:
			ir = (Irule*)it;
			yy = y + RULESP;
			draw(im, Rect(x, yy, x + ir->width, yy + ir->size), display->black, nil, ZP);
			break;
		case Iimagetag:
			ii = (Iimage*)it;
			yy = y;
			if(ii->align == ALbottom)
				yy += l->ascent - ii->imheight;
			else if(ii->align == ALmiddle)
				yy += l->ascent - (ii->imheight/2);
			drawimg(f, Pt(x, yy), ii);
			break;
		case Iformfieldtag:
			ff = ((Iformfield*)it)->formfield;
			if(ff->ctlid >= 0) {
				ctl = f->controls[ff->ctlid];
				dims = subpt(ctl->r.max, ctl->r.min);
				yy = y + l->ascent - it->ascent;
				p = Pt(x, yy);
				ctl->r = Rpt(p, addpt(p, dims));
				drawctl(ctl, 0);
			}
			break;
		case Itabletag:
			drawtable(f, lay, Pt(x, y), ((Itable*)it)->table);
			break;
		case Ifloattag:
			ifl = (Ifloat*)it;
			xx = layorigin.x + lay->margin;
			if(ifl->side == ALright) {
				xx -= ifl->x;
				// for main layout of frame, floats hug
				// right edge of frame, not layout
				// (other browsers do that)
				if(f->layout == lay)
					xx += lay->targetwidth;
				else
					xx += lay->width;
			}
			else
				xx += ifl->x;
			switch(ifl->item->tag) {
			case Iimagetag:
				ii = (Iimage*)ifl->item;
				drawimg(f, Pt(xx, layorigin.y + ifl->y + (ii->border + ii->vspace)), ii);
				break;
			case Itabletag:
				drawtable(f, lay, Pt(xx, layorigin.y + ifl->y), ((Itable*)ifl->item)->table);
				break;
			}
			break;
		}
		x += it->width;
	}
}

static void
drawimg(Frame* f, Point iorigin, Iimage* i)
{
	CImage*	ci;
	Image*	im;
	Canimimage*	ac;
	Control*	c;
	Point	dims;
	MaskedImage*	mim;
	int	bdcol;
	Rectangle	r;
	Font*	fnt;
	int	yy;
	int	xx;
	int	col;
	Image*	fgi;

	ci = i->ci;
	im = f->cim;
	iorigin.x += i->hspace + i->border;
	// y coord is already adjusted for border and vspace
	if(ci->mims != nil) {
		r = Rpt(iorigin, addpt(iorigin, Pt(i->imwidth, i->imheight)));
		if(i->ctlid >= 0) {
			// animated
			c = f->controls[i->ctlid];
			dims = subpt(c->r.max, c->r.min);
			c->r = Rpt(iorigin, addpt(iorigin, dims));
			if(c->tag == Canimimagetag) {
				ac = (Canimimage*)c;
				ac->redraw = 1;
				ac->bg = f->layout->background;
			}
			drawctl(c, 0);
		}
		else {
			mim = ci->mims[0];
			iorigin = addpt(iorigin, mim->origin);
			draw(im, r, mim->im, mim->mask, ZP);
		}
		if(i->border) {
			if(i->anchorid != 0)
				bdcol = f->doc->link;
			else
				bdcol = Black;
			drawborder(im, r, i->border, bdcol);
		}
	}
	else if(config.imagelvl == ImgNone && i->altrep != nil) {
		fnt = fonts[DefFnt].f;
		yy = iorigin.y + (i->imheight - fnt->height)/2;
		xx = iorigin.x + (i->width - runestringwidth(fnt, i->altrep))/2;
		if(i->anchorid != 0)
			col = f->doc->link;
		else
			col = DarkGrey;
		fgi = colorimage(col);
		runestring(im, Pt(xx, yy), fgi, ZP, fnt, i->altrep);
	}
}

static void
drawtable(Frame* f, Lay* parentlay, Point torigin, Table* tab)
{
	Image*	im;
	int	hsp;
	int	vsp;
	int	pad;
	int	bd;
	int	cbd;
	int	hsep;
	int	vsep;
	int	x;
	int	y;
	int	capy;
	int	boxy;
	Image*	bgi;
	int	n;
	Tablecell*	c;
	Lay*	clay;
	int	cx;
	int	cy;
	int	wd;
	int	ht;
	Lay*	caplay;
	int	capx;

	if(tab->ncol == 0 || tab->nrow == 0)
		return ;
	im = f->cim;
	tableparams(tab, &hsp, &vsp, &pad, &bd, &cbd, &hsep, &vsep);
	x = torigin.x;
	y = torigin.y;
	capy = y;
	boxy = y;
	if(tab->caption_place == ALbottom)
		capy = y + tab->toth - tab->caph + vsp;
	else
		boxy = y + tab->caph;
	if(tab->background.image != parentlay->background.image ||
	   tab->background.color != parentlay->background.color) {
		bgi = colorimage(tab->background.color);
		draw(im, Rect(x, boxy, x + tab->totw, boxy + tab->toth - tab->caph), bgi, nil, ZP);
	}
	if(bd != 0)
		drawborder(im, Rect(x+bd, boxy+bd, x+tab->totw-bd, boxy+tab->toth-tab->caph-bd), 1, Black);
	for(c = tab->cells; c != nil; c = c->next) {
		clay = c->lay;
		if(clay == nil)
			continue;
		cx = x + tab->cols[c->col].pos.x;
		cy = y + tab->rows[c->row].pos.y;
		wd = cellwidth(tab, c, hsep);
		ht = cellheight(tab, c, vsep);
		if(c->background.color != tab->background.color) {
			bgi = colorimage(c->background.color);
			draw(im, Rect(cx-pad, cy-pad, cx+wd+pad, cy+ht+pad), bgi, nil, ZP);
		}
		if(bd != 0)
			drawborder(im, Rect(cx-pad+1, cy-pad+1, cx+wd+pad-1, cy+ht+pad-1), 1, Black);
		if(c->align.valign != ALtop && c->align.valign != ALbaseline) {
			n = ht - clay->height;
			if(c->align.valign == ALmiddle)
				cy += n/2;
			else if(c->align.valign == ALbottom)
				cy += n;
		}
		if(dbgtab)
			trace("drawtable %d cell %d at (%d,%d)\n", tab->tableid, c->cellid, cx, cy);
		drawlay(f, clay, Pt(cx, cy));
	}
	if(tab->caption_lay != nil) {
		caplay = tab->caption_lay;
		capx = x;
		if(caplay->width < tab->totw)
			capx += (tab->totw - caplay->width)/2;
		drawlay(f, caplay, Pt(capx, capy));
	}
}

// Draw border of width n just outside r, using src color
void
drawborder(Image* im, Rectangle r, int n, int color)
{
	int	x;
	int	y;
	int	xr;
	int	ybi;
	Image*	src;

	x = r.min.x - n;
	y = r.min.y - n;
	xr = r.max.x + n;
	ybi = r.max.y;
	src = colorimage(color);
	draw(im, Rect(x, y, xr, y + n), src, nil, ZP);			// top
	draw(im, Rect(x, ybi, xr, ybi + n), src, nil, ZP);		// bottom
	draw(im, Rect(x, y + n, x + n, ybi), src, nil, ZP);		// left
	draw(im, Rect(xr - n, y + n, xr, ybi), src, nil, ZP);	// right
}

// Draw relief border just outside r, width 2 border,
// colors white/lightgrey/darkgrey/black
// to give raised relief (if raised != 0) or sunken.
void
drawrelief(Image* im, Rectangle r, int raised)
{
	int	x;
	int	x1;
	int	x2;
	int	xr;
	int	xr1;
	int	xr2;
	int	y;
	int	y1;
	int	y2;
	int	yb;
	int	yb1;
	int	yb2;
	Image*	tlo;
	Image*	tli;
	Image*	bro;
	Image*	bri;

	// ((x,y),(xr,yb)) == r
	x = r.min.x;
	x1 = x - 1;
	x2 = x - 2;
	xr = r.max.x;
	xr1 = xr + 1;
	xr2 = xr + 2;
	y = r.min.y;
	y1 = y - 1;
	y2 = y - 2;
	yb = r.max.y;
	yb1 = yb + 1;
	yb2 = yb + 2;

	// colors for top/left outside, top/left inside, bottom/right outside, bottom/right inside
	if(raised) {
		tlo = colorimage(Grey);
		tli = colorimage(White);
		bro = colorimage(Black);
		bri = colorimage(DarkGrey);
	}
	else {
		tlo = colorimage(DarkGrey);
		tli = colorimage(Black);
		bro = colorimage(White);
		bri = colorimage(Grey);
	}
	draw(im, Rect(x2, y2, xr1, y1), tlo, nil, ZP);		// top outside
	draw(im, Rect(x1, y1, xr, y), tli, nil, ZP);			// top inside
	draw(im, Rect(x2, y1, x1, yb1), tlo, nil, ZP);		// left outside
	draw(im, Rect(x1, y, x, yb), tli, nil, ZP);			// left inside
	draw(im, Rect(xr, y1, xr1, yb), bri, nil, ZP);		// right inside
	draw(im, Rect(xr1, y, xr2, yb1), bro, nil, ZP);		// right outside
	draw(im, Rect(x1, yb, xr1, yb1), bri, nil, ZP);		// bottom inside
	draw(im, Rect(x, yb1, xr2, yb2), bro, nil, ZP);		// bottom outside
}

// Fill r with color
void
drawfill(Image* im, Rectangle r, int color)
{
	draw(im, r, colorimage(color), nil, ZP);
}

// Draw string in default font at p
void
drawstring(Image* im, Point p, Rune* s)
{
	runestring(im, p, colorimage(Black), ZP, fonts[DefFnt].f, s);
}

// Return (width, height) of string in default font
Point
measurestring(Rune* s)
{
	Font*	f;

	f = fonts[DefFnt].f;
	return Pt(runestringwidth(f, s), f->height);
}

// Mark as "changed" everything with change flags on the loc path
static void
markchanges(Loc* loc)
{
	int	i;
	Item*	it;
	Tablecell*	c;
	Lay*	clay;

	for(i = 0; i < loc->n; i++) {
		switch(loc->le[i].kind) {
		case LEframe:
			loc->le[i].frame->layout->flags |= Lchanged;
			break;
		case LEline:
			loc->le[i].line->flags |= Lchanged;
			break;
		case LEitem:
			it = loc->le[i].item;
			switch(it->tag) {
			case Itabletag:
				((Itable*)it)->table->flags |= Lchanged;
				break;
			case Ifloattag:
				// whole layout will be redone if layout changes
				// and there are any floats
				break;
			}
			break;
		case LEtablecell:
			c = loc->le[i].tcell;
			clay = c->lay;
			if(clay != nil)
				clay->flags |= Lchanged;
			break;
		}
	}
}

static Image*
colorimage(int rgb)
{
	Image*	im;
	int	hv;
	Colornode*	xhd;
	Colornode*	x;

	if(rgb == Black)
		return display->black;
	else if(rgb == White)
		return display->white;
	else {
		hv = rgb%NCOLHASH;
		xhd = colorhashtab[hv];
		x = xhd;
		while(x != nil && x->rgb != rgb)
			x = x->next;
		if(x == nil) {
			im = allocimage(display, Rect(0,0,1,1), screen->chan, 1, (rgb<<8)|0xFF);
			if(im == nil) {
				trace("can't allocate color! %x, chan %d\n", rgb, screen->chan);
				im = display->black;
			}
			x = newcolornode(rgb, im, xhd);
			colorhashtab[hv] = x;
		}
		return x->im;
	}
}

static Colornode*
newcolornode(int rgb, Image* im, Colornode* next)
{
	Colornode* c;

	c = (Colornode*)emalloc(sizeof(Colornode));
	c->rgb = rgb;
	c->im = im;
	c->next = next;
	return c;
}

// Use f->background.image (if not nil) or f->background.color to fill r (in cim coord system)
// with background color.
static void
fillbg(Frame* f, Rectangle r)
{
	Image*	bgi;
	CImage*	bgci;

	bgci = f->doc->background.image;
	bgi = nil;
	if(bgci != nil && bgci->mims != nil)
		bgi = bgci->mims[0]->im;
	if(bgi == nil)
		bgi = colorimage(f->doc->background.color);
	draw(f->cim, r, bgi, nil, f->viewr.min);
}

// Draw triangle pointing in direction given by kind (TRlup, etc.)
// Assume r is a square
static void
drawtriangle(Image* im, Rectangle r, int kind, int style)
{
	int	b;
	int	b2;
	int	bm2;
	Point	p[3];
	Image*	col012;
	Image*	col20;
	Image*	d;
	Image*	l;
	int	i;
	Image*	t;

	drawfill(im, r, Grey);
	b = r.max.x - r.min.x;
	if(b < 4)
		return ;
	b2 = b/2;
	bm2 = b - ReliefBd;
	d = colorimage(DarkGrey);
	l = colorimage(White);
	col012 = d;
	col20 = l;
	switch(kind) {
	case TRIup:
		p[0] = Pt(b2, ReliefBd);
		p[1] = Pt(bm2, bm2);
		p[2] = Pt(ReliefBd, bm2);
		break;
	case TRIdown:
		p[0] = Pt(b2, bm2);
		p[1] = Pt(ReliefBd, ReliefBd);
		p[2] = Pt(bm2, ReliefBd);
		col012 = l;
		col20 = d;
		break;
	case TRIleft:
		p[0] = Pt(bm2, ReliefBd);
		p[1] = Pt(bm2, bm2);
		p[2] = Pt(ReliefBd, b2);
		break;
	case TRIright:
		p[0] = Pt(ReliefBd, bm2);
		p[1] = Pt(ReliefBd, ReliefBd);
		p[2] = Pt(bm2, b2);
		col012 = l;
		col20 = d;
		break;
	}
	if(style == ReliefSunk) {
		t = col012;
		col012 = col20;
		col20 = t;
	}
	for(i = 0; i < 3; i++)
		p[i] = addpt(p[i], r.min);
	fillpoly(im, p, 3, ~0, colorimage(Grey), ZP);
	line(im, p[0], p[1], 0, 0, ReliefBd/2, col012, ZP);
	line(im, p[1], p[2], 0, 0, ReliefBd/2, col012, ZP);
	line(im, p[2], p[0], 0, 0, ReliefBd/2, col20, ZP);
}

static void
flushc(Frame* f)
{
	USED(f);
	flushimage(display, 1);
}

Frame*
newframe()
{
	Frame*	f;

	f = (Frame*)emallocz(sizeof(Frame));
	f->parent = nil;
	f->cim = nil;
	f->r = Rect(0, 0, 0, 0);
	resetframe(f);
	return f;
}

Framelist*
newframelist(Frame* f, Framelist* l)
{
	Framelist* fl;

	fl = (Framelist*)emalloc(sizeof(Framelist));
	fl->val = f;
	fl->next = l;
	return fl;
}

Frame*
newkid(Frame* parent, Kidinfo* ki, Rectangle r)
{
	Frame*	f;

	f = (Frame*)emallocz(sizeof(Frame));
	f->parent = parent;
	f->cim = parent->cim;
	f->r = r;
	resetframe(f);
	f->src = ki->src;
	f->name = ki->name;
	f->marginw = ki->marginw;
	f->marginh = ki->marginh;
	f->framebd = ki->framebd;
	f->flags = ki->flags;
	return f;
}

// Note: f->parent, f->cim and f->r should not be reset
// And if f->parent is true, don't reset params set in frameset.
void
resetframe(Frame* f)
{
	f->id = ++frameid;
	f->doc = nil;
	if(f->parent == nil) {
		f->src = nil;
		f->name = nil;
		f->marginw = FRMARGIN;
		f->marginh = FRMARGIN;
		f->framebd = 0;
		f->flags = FRvscroll|FRhscrollauto;
	}
	f->layout = nil;
	f->controls = nil;
	f->controlslen = 0;
	f->controlid = 0;
	f->cr = f->r;
	f->viewr = Rect(0, 0, 0, 0);
	f->totalr = f->viewr;
	f->vscr = nil;
	f->hscr = nil;
	f->kids = nil;
}

int
addcontrol(Frame* f, Control* c)
{
	int	ans;

	if(f->controlslen <= f->controlid) {
		f->controlslen += 30;
		f->controls = (Control**)erealloc(f->controls, f->controlslen * sizeof(Control*));
	}
	f->controls[f->controlid] = c;
	ans = f->controlid++;
	return ans;
}

void
xscroll(Frame* f, int kind, int val)
{
	int	newx;

	newx = f->viewr.min.x;
	switch(kind) {
	case CAscrollpage:
		newx += val*(Dx(f->cr)*8/10);
		break;
	case CAscrollline:
		newx += val*Dx(f->cr)/10;
		break;
	case CAscrolldelta:
		newx += val*f->totalr.max.x/Dx(f->cr);
		break;
	case CAscrollabs:
		newx = val;
		break;
	}
	newx = max(0, min(newx, f->totalr.max.x));
	if(newx != f->viewr.min.x) {
		f->viewr.min.x = newx;
		fixframegeom(f);
		drawall(f);
	}
}

// Don't actually scroll by "page" and "line",
// But rather, 80% and 10%, which give more
// context in the first case, and more motion
// in the second.
void
yscroll(Frame* f, int kind, int val)
{
	int	newy;

	newy = f->viewr.min.y;
	switch(kind) {
	case CAscrollpage:
		newy += val*(Dy(f->cr)*8/10);
		break;
	case CAscrollline:
		newy += val*Dy(f->cr)/10;
		break;
	case CAscrolldelta:
		newy += val*f->totalr.max.y/Dy(f->cr);
		break;
	case CAscrollabs:
		newy = val;
		break;
	}
	newy = max(0, min(newy, f->totalr.max.y));
	if(newy != f->viewr.min.y) {
		f->viewr.min.y = newy;
		fixframegeom(f);
		drawall(f);
	}
}

// Convert layout coords (where (0,0) is top left of layout)
// to screen coords (i.e., coord system of mouse, f->cr, etc.)
Point
sptolp(Frame* f, Point sp)
{
	return addpt(f->viewr.min, subpt(sp, f->cr.min));
}

// Reverse translation of sptolp
Point
lptosp(Frame* f, Point lp)
{
	return addpt(lp, subpt(f->cr.min, f->viewr.min));
}

// Return Loc of Item or Scrollbar containing p (p in screen coords)
// or item it, if that is not nil.
Loc*
findloc(Frame* f, Point p, Item* it)
{
	return framefind(newloc(), f, p, it);
}

// Find it (if non-nil) or place where p is (known to be inside f's layout).
static Loc*
framefind(Loc* loc, Frame* f, Point p, Item* it)
{
	Frame*	kf;
	Loc*	try;
	Framelist*	fl;
	Lay*	lay;

	addloc(loc, LEframe, f->r.min);
	loc->le[loc->n - 1].frame = f;
	if(it == nil) {
		if(f->vscr != nil && ptinrect(p, f->vscr->r)) {
			addloc(loc, LEcontrol, f->vscr->r.min);
			loc->le[loc->n - 1].control = f->vscr;
			loc->pos = subpt(p, f->vscr->r.min);
			return loc;
		}
		if(f->hscr != nil && ptinrect(p, f->hscr->r)) {
			addloc(loc, LEcontrol, f->hscr->r.min);
			loc->le[loc->n - 1].control = f->hscr;
			loc->pos = subpt(p, f->hscr->r.min);
			return loc;
		}
	}
	if(it != nil || ptinrect(p, f->cr)) {
		lay = f->layout;
		if(f->kids != nil) {
			for(fl = f->kids; fl != nil; fl = fl->next) {
				kf = fl->val;
				try = framefind(loc, kf, p, it);
				if(try != nil)
					return try;
			}
		}
		else if(lay != nil)
			return layfind(loc, f, lay, lptosp(f, ZP), p, it);
	}
	return nil;
}

// Find it (if non-nil) or place where p is (known to be inside f's layout).
// p (in screen coords), lay offset by origin also in screen coords
static Loc*
layfind(Loc* loc, Frame* f, Lay* lay, Point origin, Point p, Item* it)
{
	Ifloat*	flist;
	Line*	l;
	Loc*	lloc;
	Ifloat*	fl;
	int	fymin;
	int	fymax;
	int	inside;
	int	xx;
	Point	fp;
	int	match;
	Point	o;

	for(flist = lay->floats; flist != nil; flist = flist->nextfloat) {
		fl = flist;
		fymin = fl->y + origin.y;
		fymax = fymin + fl->item->height;
		inside = 0;
		xx = 0;
		if(it != nil || (fymin <= p.y && p.y < fymax)) {
			xx = origin.x + lay->margin;
			if(fl->side == ALright) {
				if(lay == f->layout)
					xx += Dx(f->cr) - fl->x;
				else
					xx += lay->width - fl->x;
			}
			else
				xx += fl->x;
			if(p.x >= xx && p.x < xx + fl->item->width)
				inside = 1;
		}
		fp = Pt(xx, fymin);
		match = 0;
		if(it != nil) {
			switch(fl->item->tag) {
			case Itabletag:
				addloc(loc, LEitem, fp);
				loc->le[loc->n - 1].item = (Item*)fl;
				loc->pos = subpt(p, fp);
				lloc = tablefind(loc, f, (Itable*)(fl->item), fp, p, it);
				if(lloc != nil)
					return lloc;
				break;
			case Iimagetag:
				match = (it == (Item*)fl || it == fl->item);
				break;
			}
		}
		if(match || inside) {
			addloc(loc, LEitem, fp);
			loc->le[loc->n - 1].item = (Item*)fl;
			loc->pos = subpt(p, fp);
			if(it == fl->item) {
				addloc(loc, LEitem, fp);
				loc->le[loc->n - 1].item = fl->item;
			}
			if(inside) {
				if(fl->item->tag == Itabletag)
					loc = tablefind(loc, f, (Itable*)(fl->item), fp, p, it);
			}
			return loc;
		}
	}
	for(l = lay->start; l != nil; l = l->next) {
		o = addpt(origin, l->pos);
		if(it != nil || (o.y <= p.y && p.y < o.y + l->height)) {
			lloc = linefind(loc, f, l, o, p, it);
			if(lloc != nil)
				return lloc;
			if(it == nil && o.y + l->height >= p.y)
				break;
		}
	}
	return nil;
}

// p (in screen coords), line at o, also in screen coords
static Loc*
linefind(Loc* loc, Frame* f, Line* l, Point o, Point p, Item* it)
{
	int	x;
	int	y;
	Item*	i;
	Font*	fnt;
	Loc*	lloc;
	Itext*	ti;
	Iimage*	ii;
	Iformfield*	fi;
	int	yy;
	int	h;

	addloc(loc, LEline, o);
	loc->le[loc->n - 1].line = l;
	x = o.x;
	y = o.y;
	for(i = l->items; i != nil; i = i->next) {
		if(it != nil || (x <= p.x && p.x < x + i->width)) {
			yy = y;
			h = 0;
			switch(i->tag) {
			case Itexttag:
				ti = (Itext*)i;
				fnt = fonts[ti->fnt].f;
				yy += l->ascent - fnt->ascent + (ti->voff) - Voffbias;
				h = fnt->height;
				break;
			case Iruletag:
				h = ((Irule*)i)->size;
				break;
			case Iimagetag:
				ii = (Iimage*)i;
				yy = y;
				if(ii->align == ALbottom)
					yy += l->ascent - ii->imheight;
				else if(ii->align == ALmiddle)
					yy += l->ascent - (ii->imheight/2);
				h = ii->imheight;
				break;
			case Iformfieldtag:
				fi = (Iformfield*)i;
				h = fi->height;
				yy += l->ascent - fi->ascent;
				if(it != nil) {
					if(it == fi->formfield->image) {
						addloc(loc, LEitem, Pt(x, yy));
						loc->le[loc->n - 1].item = i;
						addloc(loc, LEitem, Pt(x, yy));
						loc->le[loc->n - 1].item = it;
						loc->pos = ZP;
						return loc;
					}
				}
				else if(yy < p.y && p.y < yy + h && fi->formfield->ctlid >= 0) {
					addloc(loc, LEcontrol, Pt(x, yy));
					loc->le[loc->n - 1].control = f->controls[fi->formfield->ctlid];
					loc->pos = subpt(p, Pt(x, yy));
					return loc;
				}
				break;
			case Itabletag:
				lloc = tablefind(loc, f, (Itable*)i, Pt(x, y), p, it);
				if(lloc != nil)
					return lloc;
				break;
			}
			if(it == i || (it == nil && yy <= p.y && p.y < yy + h)) {
				addloc(loc, LEitem, Pt(x, yy));
				loc->le[loc->n - 1].item = i;
				loc->pos = subpt(p, Pt(x, yy));
				return loc;
			}
			if(it == nil)
				return nil;
		}
		x += i->width;
		if(it == nil && x >= p.x)
			break;
	}
	loc->n--;
	return nil;
}

static Loc*
tablefind(Loc* loc, Frame* f, Itable* ti, Point torigin, Point p, Item* it)
{
	Table*	t;
	int	hsp;
	int	vsp;
	int	pad;
	int	bd;
	int	cbd;
	int	hsep;
	int	vsep;
	Lay*	caplay;
	int	capy;
	Loc*	lloc;
	int	n;
	Tablecell*	c;
	Lay*	clay;
	int	cx;
	int	cy;
	int	wd;
	int	ht;

	addloc(loc, LEitem, torigin);
	loc->le[loc->n - 1].item = (Item*)ti;
	t = ti->table;
	tableparams(t, &hsp, &vsp, &pad, &bd, &cbd, &hsep, &vsep);
	caplay = t->caption_lay;
	if(caplay != nil) {
		capy = torigin.y;
		if(t->caption_place == ALbottom)
			capy += t->toth - t->caph + vsp;
		lloc = layfind(loc, f, caplay, Pt(torigin.x, capy), p, it);
		if(lloc != nil)
			return lloc;
	}
	for(c = t->cells; c != nil; c = c->next) {
		clay = c->lay;
		if(clay == nil)
			continue;
		cx = torigin.x + t->cols[c->col].pos.x;
		cy = torigin.y + t->rows[c->row].pos.y;
		wd = cellwidth(t, c, hsep);
		ht = cellheight(t, c, vsep);
		if(it == nil && !ptinrect(p, Rect(cx, cy, cx + wd, cy + ht)))
			continue;
		if(c->align.valign != ALtop && c->align.valign != ALbaseline) {
			n = ht - clay->height;
			if(c->align.valign == ALmiddle)
				cy += n/2;
			else if(c->align.valign == ALbottom)
				cy += n;
		}
		addloc(loc, LEtablecell, Pt(cx, cy));
		loc->le[loc->n - 1].tcell = c;
		lloc = layfind(loc, f, clay, Pt(cx, cy), p, it);
		if(lloc != nil)
			return lloc;
		loc->n--;
		if(it == nil)
			return nil;
	}
	loc->n--;
	return nil;
}

Control*
newff(Frame* f, Formfield* ff)
{
	Control*	ans;
	int	nh;
	int	nv;
	Image*	pic;
	Image*	picmask;
	Rune*	lab;
	Iimage*	i;
	Option*	o;
	Option*	ao;
	int	k;
	int	nvis;
	int	n;
	int	linewrap;

	ans = nil;
	switch(ff->ftype) {
	case Ftext:
	case Fpassword:
	case Ftextarea:
		nh = ff->size;
		nv = 1;
		linewrap = 0;
		if(ff->ftype == Ftextarea) {
			nh = ff->cols;
			nv = ff->rows;
			linewrap = 1;
		}
		ans = newentry(f, nh, nv, linewrap);
		entryset(ans, ff->value);
		break;
	case Fcheckbox:
	case Fradio:
		ans = newcheckbox(f, ff->ftype == Fradio);
		if(ff->flags&FFchecked)
			ans->flags |= CFactive;
		break;
	case Fsubmit:
	case Fimage:
	case Freset:
	case Fbutton:
		if(ff->image == nil)
			ans = newbutton(f, nil, nil, ff->value, nil, 0, 1);
		else {
			if(ff->image->tag == Iimagetag) {
				i = (Iimage*)(ff->image);
				pic = nil;
				picmask = nil;
				if(i->ci->mims != nil) {
					pic = i->ci->mims[0]->im;
					picmask = i->ci->mims[0]->mask;
				}
				lab = nil;
				if((config).imagelvl == ImgNone) {
					lab = i->altrep;
					i = nil;
				}
				ans = newbutton(f, pic, picmask, lab, i, 0, 0);
			}
		}
		break;
	case Fselect:
		n = listlen((List*)ff->options);
		if(n > 0) {
			ao = (Option*)emalloc(n * sizeof(Option));
			o = ff->options;
			for(k = 0; k < n; k++) {
				ao[k].selected = o->selected;
				ao[k].value = o->value;
				ao[k].display = o->display;
				o = o->next;
			}
			nvis = ff->size;
			if(nvis == 0)
				nvis = min(n, 4);
			ans = newselect(f, nvis, ao, n);
		}
		break;
	case Ffile:
		if(dbglay)
			trace("warning: unimplemented file form field\n");
		break;
	}
	if(ans != nil)
		ans->ff = ff;
	return ans;
}

Control*
newscroll(Frame* f, int isvert, int length, int breadth)
{
	Point	maxpt;
	int	flags;
	Cscrollbar *sb;

	// need room for at least two squares and 2 borders of size 2
	if(length < 12) {
		breadth = 0;
		length = 0;
	}
	else if(breadth*2 + 4 > length)
		breadth = (length - 4)/2;
	;
	flags = CFenabled;
	if(isvert) {
		maxpt = Pt(breadth, length);
		flags |= CFscrvert;
	}
	else
		maxpt = Pt(length, breadth);
	sb = (Cscrollbar*)emallocz(sizeof(Cscrollbar));
	sb->tag = Cscrollbartag;
	sb->f = f;
	sb->r = Rpt(ZP, maxpt);
	sb->flags = flags;
	return (Control*)sb;
}

Control*
newentry(Frame* f, int nh, int nv, int linewrap)
{
	int	w;
	int	h;
	Centry* e;

	w = ctlcharspace*nh + 2*ENTHMARGIN;
	h = ctllinespace*nv + 2*ENTVMARGIN;
	e = (Centry*)emallocz(sizeof(Centry));
	e->tag = Centrytag;
	e->f = f;
	e->r = Rect(0, 0, w, h);
	e->flags = CFenabled;
	e->linewrap = linewrap;
	return (Control*)e;
}

Control*
newbutton(Frame* f, Image* pic, Image* picmask, Rune* lab, Iimage* it, int candisable, int dorelief)
{
	Image*	dpic;
	Image*	dpicmono;
	Image*	dpicmask;
	int	w;
	int	h;
	Rectangle	r;
	Cbutton*	b;

	if(pic != nil) {
		w = Dx(pic->r);
		h = Dy(pic->r);
	}
	else if(it != nil) {
		w = it->imwidth;
		h = it->imheight;
	}
	else {
		w = runestringwidth(fonts[CtlFnt].f, lab);
		h = ctllinespace;
	}
	if(dorelief) {
		// form image buttons are shown without margins in other browsers
		w += 2*BUTMARGIN;
		h += 2*BUTMARGIN;
	}
	r = Rect(0, 0, w, h);
	dpic = nil;
	dpicmask = nil;
	if(candisable && pic != nil) {
		// make "greyed out" image:
		//	- convert pic to monochrome (black where pic is non-white)
		//	- draw pic in White, then DarkGrey shifted (-1,-1) and use
		//	    union of those two areas as mask
		dpicmask = allocimage(display, pic->r, GREY1, 0, DOpaque);
		dpicmono = allocimage(display, pic->r, GREY1, 0, DWhite);
		draw(dpicmono, dpicmono->r, pic, display->opaque, ZP);
		// leave DOpaque in dpicmask only where mono pic is black (==transparent)
		draw(dpicmask, dpicmask->r, display->transparent, dpicmono, ZP);
		dpic = allocimage(display, pic->r, pic->chan, 0, DWhite);
		// draw(dpic, dpic->r, colorimage(White), dpicmask, ZP);
		draw(dpic, rectaddpt(dpic->r, Pt(-1, -1)), colorimage(DarkGrey), dpicmask, ZP);
		draw(dpicmask, rectaddpt(dpicmask->r, Pt(-1, -1)), display->opaque, dpicmask, ZP);
		freeimage(dpicmono);
	}
	b = (Cbutton*)emallocz(sizeof(Cbutton));
	b->tag = Cbuttontag;
	b->f = f;
	b->r = r;
	b->flags = CFenabled;
	b->pic = pic;
	b->picmask = picmask;
	b->dpic = dpic;
	b->dpicmask = dpicmask;
	b->label = lab;
	b->dorelief = dorelief;
	return (Control*)b;
}

Control*
newcheckbox(Frame* f, int isradio)
{
	Ccheckbox* cb;

	cb = (Ccheckbox*)emallocz(sizeof(Ccheckbox));
	cb->tag = Ccheckboxtag;
	cb->f = f;
	cb->r = Rect(0, 0, CBOXWID, CBOXHT);
	cb->flags = CFenabled;
	cb->isradio = isradio;
	return (Control*)cb;
}

Control*
newselect(Frame* f, int nvis, Option* options, int noptions)
{
	Font*	fnt;
	int	w;
	int	i;
	int	h;
	Control*	scr;
	Cselect*	ans;
	Cscrollbar*	pscr;

	fnt = fonts[CtlFnt].f;
	w = 0;
	for(i = 0; i < noptions; i++)
		w = max(w, runestringwidth(fnt, options[i].display));
	w += 2*SELMARGIN;
	h = ctllinespace*nvis + 2*SELMARGIN;
	scr = nil;
	if(nvis < noptions) {
		scr = newscroll(f, 1, h, SCRFBREADTH);
		scr->r = rectaddpt(scr->r, Pt(w, 0));
		w += SCRFBREADTH;
	}
	pscr = (Cscrollbar*)scr;
	ans = (Cselect*)emallocz(sizeof(Cselect));
	ans->tag = Cselecttag;
	ans->f = f;
	ans->r = Rect(0, 0, w, h);
	ans->flags = CFenabled;
	ans->scr = pscr;
	ans->nvis = nvis;
	ans->options = options;
	ans->noptions = noptions;
	if(scr != nil) {
		pscr->ctl = (Control*)ans;
		scrollset(scr, 0, nvis, noptions, 1);
	}
	return (Control*)ans;
}

Control*
newanimimage(Frame* f, CImage* cim, Background bg)
{
	Canimimage *a;

	a = (Canimimage*)emallocz(sizeof(Canimimage));
	a->tag = Canimimagetag;
	a->f = f;
	a->r = Rect(0, 0, cim->width, cim->height);
	a->cim = cim;
	a->bg = bg;
	return (Control*)a;
}

Control*
newprogbox(Frame* f)
{
	Cprogbox *b;

	b = (Cprogbox*)emallocz(sizeof(Cprogbox));
	b->tag = Cprogboxtag;
	b->f = f;
	b->r = Rect(0, 0, PBOXWID, PBOXHT);
	b->flags = CFenabled;
	b->state = Punused;
	b->bsid = -1;
	return (Control*)b;
}

Control*
newlabel(Frame* f, Rune* s)
{
	int	w;
	int	h;
	Clabel* l;

	w = runestringwidth(fonts[CtlFnt].f, s);
	h = ctllinespace + 2*ENTVMARGIN;	// give it same height as an entry box
	l = (Clabel*)emallocz(sizeof(Clabel));
	l->tag = Clabeltag;
	l->f = f;
	l->r = Rect(0, 0, w, h);
	l->s = s;
	return (Control*)l;
}

void
disable(Control* c)
{
	if(c->flags&CFenabled) {
		c->flags &= ~CFenabled;
		if(c->f->cim != nil)
			drawctl(c, 1);
	}
}

void
enable(Control* c)
{
	if(!(c->flags&CFenabled)) {
		c->flags |= CFenabled;
		if(c->f->cim != nil)
			drawctl(c, 1);
	}
}

void
losefocus(Control* c)
{
	if(c->flags&CFhasfocus) {
		c->flags &= ~CFhasfocus;
		if(c->f->cim != nil)
			drawctl(c, 1);
	}
}

void
gainfocus(Control* c)
{
	if(!(c->flags&CFhasfocus)) {
		c->flags |= CFhasfocus;
		if(c->f->cim != nil)
			drawctl(c, 1);
	}
}

void
scrollset(Control* c, int v1, int v2, int vmax, int mindelta)
{
	int	length;
	int	breadth;
	int	l;
	Cscrollbar*	sc;

	assert(c->tag == Cscrollbartag);
	sc = (Cscrollbar*)c;
	sc->mindelta = mindelta;
	if(vmax <= 0) {
		sc->top = 0;
		sc->bot = 0;
	}
	else {
		if(v1 < 0)
			v1 = 0;
		if(v2 > vmax)
			v2 = vmax;
		if(v1 > v2)
			v1 = v2;
		if(sc->flags&CFscrvert) {
			length = sc->r.max.y - sc->r.min.y;
			breadth = sc->r.max.x - sc->r.min.x;
		}
		else {
			length = sc->r.max.x - sc->r.min.x;
			breadth = sc->r.max.y - sc->r.min.y;
		}
		l = length - 2*breadth;
		assert(l >= 0);
		sc->top = l*v1/vmax;
		sc->bot = l*(vmax - v2)/vmax;
	}
	drawctl(c, 1);
}

int
dokey(Control* ctl, int keychar)
{
	int	ans;
	int	k;
	int	newcurs;
	int	slen;
	Centry*	c;

	if(!(ctl->flags&CFenabled))
		return CAnone;
	ans = CAnone;
	switch(ctl->tag) {
	case Centrytag:
		c = (Centry*)ctl;
		newcurs = -1;
		slen = Strlen(c->s);
		switch(keychar) {
		case 'a' & CTRLMASK :
			newcurs = 0;
			break;
		case 'e' & CTRLMASK:
			newcurs = slen;
			break;
		case 'f' & CTRLMASK:
			if(c->curs < slen)
				newcurs = c->curs + 1;
			break;
		case 'b' & CTRLMASK:
			if(c->curs > 0)
				newcurs = c->curs - 1;
			break;
		case 'u' & CTRLMASK:
			entrydelrange(c, 0, slen);
			break;
		case 'v' & CTRLMASK:
			entrysetfromsnarf(c);
			break;
		case 'h' & CTRLMASK:
			if(c->curs > 0)
				entrydelrange(c, c->curs - 1, c->curs);
			break;
		case DEL:
			if(c->curs < slen)
				entrydelrange(c, c->curs, c->curs + 1);
			break;
		case TAB:
			ans = CAtabkey;
			break;
		default:
			if(keychar == CR) {
				if(c->linewrap)
					keychar = '\n';
				else
					ans = CAreturnkey;
			}
			if(keychar > CTRLMASK || (keychar == '\n' && c->linewrap)) {
				c->s = (Rune*)erealloc(c->s, (slen+2)*sizeof(Rune));
				c->s[slen+1] = 0;
				for(k = slen; k > c->curs; k--)
					c->s[k] = c->s[k - 1];
				c->s[c->curs] = keychar;
				newcurs = c->curs + 1;
			}
			break;
		}
		if(newcurs >= 0) {
			c->curs = newcurs;
			entryscroll(c);
		}
		break;
	}
	return ans;
}

int
domouse(Control* ctl, Point p, int mtype)
{
	int	ans;
	int	changed;
	int	cx;
	int	x;
	Font*	fnt;
	Rune*	s;
	Rune	s1[2];
	int	i;
	int	iend;
	Control*	d;
	Formfield*	ff;
	Form*	frm;
	Formfield*	lf;
	int	n;
	int	newfirst;
	int	val;
	int	v;
	int	vmin;
	int	vmax;
	int	b;
	int	vsltop;
	int	vslbot;
	int	actflags;
	int	oldactflags;
	int	down;
	int*	linestarts;
	int	topline;
	int	cursline;
	int	nlines;
	int	lineno;
	Cbutton*	cb;
	Centry*	ce;
	Ccheckbox*	ccb;
	Cselect*	cs;
	Cscrollbar*	csb;

	if(!(ctl->flags&CFenabled))
		return CAnone;
	ans = CAnone;
	changed = 0;
	switch(ctl->tag) {
	case Cbuttontag:
		cb = (Cbutton*)ctl;
		if(mtype == Mlbuttondown) {
			cb->flags |= CFactive;
			changed = 1;
		}
		else if(mtype == Mmove && cb->ff == nil) {
			ans = CAflyover;
		}
		else if(mtype == Mlbuttonup) {
			cb->flags &= ~CFactive;
			changed = 1;
			ans = CAbuttonpush;
		}
		break;
	case Centrytag:
		ce = (Centry*)ctl;
		if(mtype == Mlbuttondown) {
			x = ce->r.min.x + ENTHMARGIN;
			fnt = fonts[CtlFnt].f;
			s = ce->s;
			s1[1] = 0;
			i = ce->left;
			iend = Strlen(s);
			if(ce->linewrap) {
				nlines = entrywrapcalc(ce, &linestarts, &topline, &cursline);
				if(nlines > 1) {
					lineno = topline + (p.y-(ce->r.min.y+ENTVMARGIN))/ctllinespace;
					if(lineno >= nlines)
						lineno = nlines-1;
					i = linestarts[lineno];
					iend = linestarts[lineno+1];
				}
			}
			for(; i < iend; i++) {
				s1[0] = s[i];
				cx = runestringwidth(fnt, s1);
				if(p.x < x + cx)
					break;
				x += cx;
			}
			ce->curs = i;
			changed = 1;
			if(!(ce->flags&CFhasfocus))
				ans = CAkeyfocus;
		}
		break;
	case Ccheckboxtag:
		ccb = (Ccheckbox*)ctl;
		if(mtype == Mlbuttonup) {
			if(ccb->isradio) {
				if(!(ccb->flags&CFactive)) {
					ccb->flags |= CFactive;
					changed = 1;
					frm = ccb->ff->form;
					for(lf = frm->fields; lf != nil; lf = lf->next) {
						ff = lf;
						if(ff == ccb->ff)
							continue;
						if(ff->ftype == Fradio && !Strcmp(ff->name, ccb->ff->name) && ff->ctlid >= 0) {
							d = ccb->f->controls[ff->ctlid];
							if(d->flags&CFactive) {
								d->flags &= ~CFactive;
								drawctl(d, 0);
								break;
							}
						}
					}
				}
			}
			else {
				ccb->flags ^= CFactive;
				changed = 1;
			}
		}
		break;
	case Cselecttag:
		cs = (Cselect*)ctl;
		if(cs->scr != nil && p.x >= cs->r.max.x - SCRFBREADTH) {
			return domouse((Control*)cs->scr, p, mtype);
		}
		else if(mtype == Mlbuttonup) {
			n = (p.y - (cs->r.min.y + SELMARGIN))/ctllinespace + cs->first;
			if(n >= 0 && n < cs->noptions) {
				cs->options[n].selected ^= 1;
				if(cs->ff != nil && !(cs->ff->flags&FFmultiple) && cs->options[n].selected) {
					for(i = 0; i < cs->noptions; i++) {
						if(i != n)
							cs->options[i].selected = 0;
					}
				}
				changed = 1;
			}
		}
		break;
	case Cscrollbartag:
		csb = (Cscrollbar*)ctl;
		val = 0;
		if(csb->flags&CFscrvert) {
			v = p.y;
			vmin = csb->r.min.y;
			vmax = csb->r.max.y;
			b = Dx(csb->r);
		}
		else {
			v = p.x;
			vmin = csb->r.min.x;
			vmax = csb->r.max.x;
			b = Dy(csb->r);
		}
		vsltop = vmin + b + csb->top;
		vslbot = vmax - b - csb->bot;
		actflags = 0;
		oldactflags = csb->flags&CFscrallact;
		down = (mtype == Mlbuttondown);
		if(v >= vsltop && v < vslbot) {
			if(mtype == Mldrag && (csb->flags&CFactive)) {
				actflags = CFactive;
				val = v - csb->dragv;
				if(abs(val) > csb->mindelta) {
					ans = CAscrolldelta;
					csb->dragv = v;
				}
			}
			else if(down || mtype == Mldrag) {
				actflags = CFactive;
				csb->dragv = v;
			}
		}
		else if(down || mtype == Mlbuttonup) {
			if(v < vmin + b) {
				if(down)
					actflags = CFscracta1;
				else {
					ans = CAscrollline;
					val = -1;
				}
			}
			else if(v < vsltop) {
				if(down)
					actflags = CFscracttr1;
				else {
					ans = CAscrollpage;
					val = -1;
				}
			}
			else if(v >= vmax - b) {
				if(down)
					actflags = CFscracta2;
				else {
					ans = CAscrollline;
					val = 1;
				}
			}
			else if(v >= vslbot) {
				if(down)
					actflags = CFscracttr2;
				else {
					ans = CAscrollpage;
					val = 1;
				}
			}
		}
		csb->flags = (csb->flags&~CFscrallact)|actflags;
		if(ans != CAnone) {
			if(csb->ctl != nil) {
				switch(csb->ctl->tag) {
				case Cselecttag:
					cs = (Cselect*)csb->ctl;
					newfirst = cs->first;
					switch(ans) {
					case CAscrollpage:
						newfirst += val*cs->nvis;
						break;
					case CAscrollline:
						newfirst += val;
						break;
					case CAscrolldelta:
						if(val > 0)
							newfirst++;
						else
							newfirst--;
						break;
					}
					newfirst = max(0, min(newfirst, cs->noptions - cs->nvis));
					cs->first = newfirst;
					scrollset((Control*)csb, newfirst, newfirst + cs->nvis, cs->noptions, 1);
					drawctl((Control*)cs, 1);
					return ans;
				}
			}
			else {
				if(csb->flags&CFscrvert)
					yscroll(csb->f, ans, val);
				else
					xscroll(csb->f, ans, val);
			}
			changed = 1;
		}
		else if(actflags != oldactflags) {
			changed = 1;
		}
		break;
	case Cprogboxtag:
		if(mtype == Mlbuttondown)
			ans = CAbuttonpush;
		break;
	}
	if(changed)
		drawctl(ctl, 1);
	return ans;
}

void
resetctl(Control* ctl)
{
	Option*	o;
	int	i;
	Centry*	ce;
	Ccheckbox*	ccb;
	Cselect*	cs;

	switch(ctl->tag) {
	case Cbuttontag:
		ctl->flags &= ~CFactive;
		break;
	case Centrytag:
		ce = (Centry*)ctl;
		ce->s = nil;
		ce->curs = 0;
		ce->left = 0;
		if(ce->ff != nil && ce->ff->value != nil)
			ce->s = ce->ff->value;
		break;
	case Ccheckboxtag:
		ccb = (Ccheckbox*)ctl;
		ccb->flags &= ~CFactive;
		if(ccb->ff != nil && !(ccb->ff->flags&FFchecked))
			ccb->flags |= CFactive;
		break;
	case Cselecttag:
		cs = (Cselect*)ctl;
		if(cs->ff != nil) {
			o = cs->ff->options;
			for(i = 0; i < cs->noptions; i++) {
				cs->options[i].selected = o->selected;
				o = o->next;
			}
		}
		cs->first = 0;
		if(cs->scr != nil) {
			scrollset((Control*)cs->scr, 0, cs->nvis, cs->noptions, 1);
		}
		break;
	case Canimimagetag:
		((Canimimage*)ctl)->cur = 0;
		break;
	}
	drawctl(ctl, 0);
}

void
drawctl(Control* ctl, int flush)
{
	Image*	win;
	Iimage*	imi;
	Image*	m;
	Image*	pic;
	Point	p;
	int	w;
	int	h;
	int	x;
	int	y;
	int	relief;
	Rectangle	cursr;
	Rune*	s;
	Font*	fnt;
	int	a;
	int	a1;
	Point	cen;
	Point	p1;
	Point	p2;
	Point	p3;
	Point	p4;
	Rectangle	ir;
	Rectangle	r;
	Image*	black;
	Image*	white;
	Image*	navy;
	int	i;
	int	xr;
	int	yt1;
	int	ys;
	int	yb;
	int	ya2;
	int	yt2;
	int	xt1;
	int	xs;
	int	xa2;
	int	xt2;
	Rectangle	ra1;
	Rectangle	rt1;
	Rectangle	rs;
	Rectangle	rt2;
	Rectangle	ra2;
	int	b;
	int	l;
	int	a1kind;
	int	a2kind;
	int	a1relief;
	int	a2relief;
	int	rsrelief;
	int	iprev;
	MaskedImage*	mim;
	Image*	bgi;
	int	bcol;
	int	rcol;
	int	xw;
	int	cursx;
	int	cursy;
	Rune**	lines;
	int*	linestarts;
	int	nlines;
	int	istart;
	int	iend;
	int	n;
	Point	q;
	Cbutton*	cb;
	Centry*	ce;
	Ccheckbox*	ccb;
	Cselect*	cs;
	Cscrollbar*	csb;
	Canimimage*	ca;
	Cprogbox*	cp;
	Clabel*	cl;

	if(!rectclip(&ctl->r, ctl->f->r))
		return;
	win = ctl->f->cim;
	pushclipr(ctl->r);
	switch(ctl->tag) {
	case Cbuttontag:
		cb = (Cbutton*)ctl;
		if(cb->ff != nil && cb->ff->image != nil && cb->pic == nil) {
			// check to see if image arrived
			// (dimensions will have been set by checkffsize, if needed;
			// this code is only for when the HTML specified the dimensions)
			imi = (Iimage*)cb->ff->image;
			assert(imi->tag == Iimagetag);
			if(imi->ci->mims != nil) {
				cb->pic = imi->ci->mims[0]->im;
				cb->picmask = imi->ci->mims[0]->mask;
			}
		}
		if(cb->dorelief || cb->pic == nil)
			draw(win, cb->r, colorimage(Grey), nil, ZP);
		if(cb->pic != nil) {
			if(cb->flags&CFenabled) {
				pic = cb->pic;
				m = cb->picmask;
			}
			else {
				pic = cb->dpic;
				m = cb->dpicmask;
			}
			w = Dx(pic->r);
			h = Dy(pic->r);
			x = cb->r.min.x + (Dx(cb->r) - w)/2;
			y = cb->r.min.y + (Dy(cb->r) - h)/2;
			if((cb->flags&CFactive) && cb->dorelief) {
				x++;
				y++;
			}
			draw(win, Rect(x, y, x + w, y + h), pic, m, ZP);
		}
		else if(cb->label != nil) {
			p = addpt(cb->r.min, Pt(BUTMARGIN, BUTMARGIN));
			if(cb->flags&CFactive)
				p = addpt(p, Pt(1, 1));
			runestring(win, p, colorimage(Black), ZP, fonts[CtlFnt].f, cb->label);
		}
		if(cb->dorelief) {
			relief = ReliefRaised;
			if(cb->flags&CFactive)
				relief = ReliefSunk;
			drawrelief(win, insetrect(cb->r, 2), relief);
		}
		break;
	case Centrytag:
		ce = (Centry*)ctl;
		draw(win, ce->r, colorimage(White), nil, ZP);
		drawrelief(win, insetrect(ce->r, 2), ReliefSunk);
		p = addpt(ce->r.min, Pt(ENTHMARGIN, ENTVMARGIN));
		s = ce->s + ce->left;
		fnt = fonts[CtlFnt].f;
		cursx = -1;
		cursy = p.y;
		if(ce->linewrap) {
			nlines = wrapstring(fnt, s, Dx(ce->r)-2*ENTHMARGIN, &lines, &linestarts);
			q = p;
			if(nlines > 0)
				cursx = 0;
			for(n = 0; n < nlines; n++) {
				s = lines[n];
				runestring(win, q, colorimage(Black), ZP, fnt, s);
				istart = linestarts[n];
				iend = linestarts[n+1];
				if(ce->curs >= istart && (ce->curs<iend || (ce->curs==iend && n == nlines-1))) {
					if(ce->curs > istart)
						cursx = runestringnwidth(fnt, s, ce->curs-ce->left);
					else
						cursx = 0;
					cursy = q.y;
				}
				q.y += ctllinespace;
			}
		}
		else {
			runestring(win, p, colorimage(Black), ZP, fnt, s);
			if(ce->curs >= ce->left)
				cursx = runestringnwidth(fnt, s, ce->curs - ce->left);
		}
		if((ce->flags&CFhasfocus) && cursx >= 0) {
			cursr = Rect(p.x + cursx - 2, cursy - 1, p.x + cursx, cursy + ctllinespace + 1);
			draw(win, cursr, colorimage(Black), nil, ZP);
		}
		break;
	case Ccheckboxtag:
		ccb = (Ccheckbox*)ctl;
		draw(win, ccb->r, colorimage(White), nil, ZP);
		if(ccb->isradio) {
			a = CBOXHT/2;
			a1 = a - 1;
			cen = Pt(ccb->r.min.x + a, ccb->r.min.y + a);
			ellipse(win, cen, a1, a1, 1, colorimage(DarkGrey), ZP);
			arc(win, cen, a, a, 0, colorimage(Black), ZP, 45, 180);
			arc(win, cen, a, a, 0, colorimage(Grey), ZP, 225, 180);
			if(ccb->flags&CFactive)
				fillellipse(win, cen, 2, 2, colorimage(Black), ZP);
		}
		else {
			ir = insetrect(ccb->r, 2);
			ir.min.x += CBOXWID - CBOXHT;
			ir.max.x -= CBOXWID - CBOXHT;
			drawrelief(win, ir, ReliefSunk);
			if(ccb->flags&CFactive) {
				p1 = Pt(ir.min.x, ir.min.y);
				p2 = Pt(ir.max.x, ir.max.y);
				p3 = Pt(ir.max.x, ir.min.y);
				p4 = Pt(ir.min.x, ir.max.y);
				line(win, p1, p2, Endsquare, Endsquare, 0, colorimage(Black), ZP);
				line(win, p3, p4, Endsquare, Endsquare, 0, colorimage(Black), ZP);
			}
		}
		break;
	case Cselecttag:
		cs = (Cselect*)ctl;
		black = colorimage(Black);
		white = colorimage(White);
		navy = colorimage(Navy);
		draw(win, cs->r, white, nil, ZP);
		drawrelief(win, insetrect(cs->r, 2), ReliefSunk);
		ir = insetrect(cs->r, SELMARGIN);
		p = ir.min;
		fnt = fonts[CtlFnt].f;
		for(i = cs->first; i < cs->noptions && i < cs->first + cs->nvis; i++) {
			if(cs->options[i].selected) {
				r = Rect(p.x - SELMARGIN, p.y, cs->r.max.x - SCRFBREADTH, p.y + ctllinespace);
				draw(win, r, navy, nil, ZP);
				runestring(win, p, white, ZP, fnt, cs->options[i].display);
			}
			else {
				runestring(win, p, black, ZP, fnt, cs->options[i].display);
			}
			p.y += ctllinespace;
		}
		if(cs->scr != nil) {
			cs->scr->r = rectsubpt(cs->scr->r, cs->scr->r.min);
			cs->scr->r = rectaddpt(cs->scr->r, Pt(cs->r.max.x - SCRFBREADTH, cs->r.min.y));
			drawctl((Control*)cs->scr, 0);
		}
		break;
	case Cscrollbartag:
		csb = (Cscrollbar*)ctl;
		x = csb->r.min.x;
		y = csb->r.min.y;
		if(csb->flags&CFscrvert) {
			l = csb->r.max.y - csb->r.min.y;
			b = csb->r.max.x - csb->r.min.x;
			xr = x + b;
			yt1 = y + b;
			ys = yt1 + csb->top;
			yb = y + l;
			ya2 = yb - b;
			yt2 = ya2 - csb->bot;
			ra1 = Rect(x, y, xr, yt1);
			rt1 = Rect(x, yt1, xr, ys);
			rs = Rect(x, ys, xr, yt2);
			rt2 = Rect(x, yt2, xr, ya2);
			ra2 = Rect(x, ya2, xr, yb);
			a1kind = TRIup;
			a2kind = TRIdown;
		}
		else {
			l = csb->r.max.x - csb->r.min.x;
			b = csb->r.max.y - csb->r.min.y;
			yb = y + b;
			xt1 = x + b;
			xs = xt1 + csb->top;
			xr = x + l;
			xa2 = xr - b;
			xt2 = xa2 - csb->bot;
			ra1 = Rect(x, y, xt1, yb);
			rt1 = Rect(xt1, y, xs, yb);
			rs = Rect(xs, y, xt2, yb);
			rt2 = Rect(xt2, y, xa2, yb);
			ra2 = Rect(xa2, y, xr, yb);
			a1kind = TRIleft;
			a2kind = TRIright;
		}
		a1relief = ReliefRaised;
		if(csb->flags&CFscracta1)
			a1relief = ReliefSunk;
		a2relief = ReliefRaised;
		if(csb->flags&CFscracta2)
			a2relief = ReliefSunk;
		drawtriangle(win, ra1, a1kind, a1relief);
		drawtriangle(win, ra2, a2kind, a2relief);
		drawfill(win, rt1, Grey);
		rs = insetrect(rs, 2);
		drawfill(win, rs, Grey);
		rsrelief = ReliefRaised;
		if(csb->flags&CFactive)
			rsrelief = ReliefSunk;
		drawrelief(win, rs, rsrelief);
		drawfill(win, rt2, Grey);
		break;
	case Canimimagetag:
		ca = (Canimimage*)ctl;
		i = ca->cur;
		if(ca->redraw)
			i = 0;
		else if(i > 0) {
			iprev = i - 1;
			if(ca->cim->mims[iprev]->bgcolor != -1) {
				i = iprev;
				// get i back to before all "reset to previous"
				// images (which will be skipped in following
				// image drawing loop)
				while(i > 0 && ca->cim->mims[i]->bgcolor == -2)
					i--;
			}
		}
		bgi = colorimage(ca->bg.color);
		if(ca->bg.image != nil && ca->bg.image->mimslen > 0)
			bgi = ca->bg.image->mims[0]->im;
		for(; i <= ca->cur; i++) {
			mim = ca->cim->mims[i];
			if(i > 0 && i < ca->cur && mim->bgcolor == -2)
				continue;
			p = addpt(ca->r.min, mim->origin);
			r = mim->im->r;
			r = Rpt(p, addpt(p, Pt(Dx(r), Dy(r))));

			// IE takes "clear-to-background" disposal method to mean
			// clear to background of HTML page, ignoring any background
			// color specified in the GIF.
			// IE clears to background before frame 0
			if(i == 0)
				draw(win, ca->r, bgi, nil, ZP);
			if(i != ca->cur && mim->bgcolor >= 0)
				draw(win, r, bgi, nil, ZP);
			else
				draw(win, r, mim->im, mim->mask, ZP);
		}
		break;
	case Cprogboxtag:
		cp = (Cprogbox*)ctl;
		if(cp->state != Punused) {
			bcol = Black;
			rcol = Grey;
			xw = (cp->pcnt*PBOXWID + 50)/100;
			if(xw > PBOXWID)
				xw = PBOXWID;
			switch(cp->state) {
			case Pstart:
				drawfill(win, cp->r, Grey);
				bcol = White;
				break;
			case Pconnected:
				bcol = Black;
				break;
			case Phavehdr:
				bcol = DarkGrey;
				break;
			case Phavedata:
				bcol = rcol = DarkGrey;
				break;
			case Pdone:
				xw = PBOXWID;
				bcol = rcol = DarkestGrey;
				break;
			case Perr:
				bcol = rcol = Red;
				xw = PBOXWID;
				break;
			case Paborted:
				bcol = rcol = Navy;
				xw = PBOXWID;
				break;
			}
			drawborder(win, insetrect(cp->r, 3), 3, bcol);
			if(rcol != Grey) {
				r = cp->r;
				r.max.x -= (PBOXWID - xw);
				drawfill(win, r, rcol);
			}
		}
		break;
	case Clabeltag:
		cl = (Clabel*)ctl;
		p = addpt(cl->r.min, Pt(0, ENTVMARGIN));
		runestring(win, p, colorimage(Black), ZP, fonts[CtlFnt].f, cl->s);
		break;
	}
	popclipr();
	if(flush)
		flushimage(display, 1);
}

// Break s up into substrings that fit in width availw
// when printing with font fnt.
// The returned linestarts array will contain the indexes into the original
// string where the corresponding line starts (which might not be simply
// the sum of the preceding lines because of cr/lf's in the original string
// which are omitted from the lines array.
// Return value is length of plines array.
// Empty lines (ending in cr) get put into the array as empty strings.
// The start indices array has an entry for the phantom next line, to avoid
// the need for special cases in the rest of the code.
static int
wrapstring(Font* fnt, Rune* s, int availw, Rune*** plines, int** plinestarts)
{
	Strlist* sl;
	List* sstartl;
	int sw;
	int n;
	int k;
	int slen;
	int done;
	int needbs;
	int origlen;
	int kincr;
	Rune* s1;
	Rune* s2;
	int w1;
	int w2;
	int s1len;
	int s2len;
	Rune** lines;
	int* linestarts;

	sl = nil;
	sstartl = nil;
	sw = runestringwidth(fnt, s);
	n = 0;
	k = 0;
	slen = Strlen(s);
	origlen = slen;
	done = 0;
	while(!done) {
		kincr = 0;
		needbs = 0;
		if(slen == 0) {
			s1 = nil;
			done = 1;
		}
		else {
			// if any newlines in s1, it's a forced break
			// (and newlines aren't to appear in result)
			splitl(s, slen, L"\n", &s1, &s1len, &s2, &s2len);
			if(s2len == 0) {
				if(sw <= availw) {
					s1 = s;
					done = 1;
				}
				else
					needbs = 1;
			}
			else {
				if(runestringnwidth(fnt,s1,s1len) <= availw) {
					s1 = Strndup(s1, s1len);
					s = Strndup(s2+1, s2len-1);
					slen = s2len-1;
					sw = runestringwidth(fnt, s);
					kincr = s1len+1;
				}
				else
					needbs = 1;
			}
			if(needbs) {
				if(breakstring(s, sw, fnt, availw, 0, &s1, &w1, &s2, &w2) < 0) {
					// no break possible
					s1 = s;
					done = 1;
				}
				else {
					s = s2;
					slen = Strlen(s);
					sw = w2;
					kincr = Strlen(s1);
				}
			}
		}
		sl = newstrlist(s1, sl);
		sstartl = newlist(k, sstartl);
		k += kincr;
		n++;
	}
	// Use arrays for return values,
	// reverse back to original order
	lines = (Rune**)emalloc(n * sizeof(Rune*));
	linestarts = (int*)emalloc((n+1) * sizeof(int));
	linestarts[n] = origlen;
	k = n;
	while(sl != nil) {
		lines[--k] = sl->val;
		linestarts[k] = sstartl->val;
		sl = sl->next;
		sstartl = sstartl->next;
	}
	*plines = lines;
	*plinestarts = linestarts;
	return n;
}

void
entryset(Control* c, Rune* s)
{
	Centry*	e;

	assert(c->tag == Centrytag);
	e = (Centry*)c;
	e->s = s;
	e->curs = 0;
	e->left = 0;
	drawctl((Control*)e, 1);
}

// delete given range of characters, and redraw
static void
entrydelrange(Centry* e, int istart, int iend)
{
	int	n;
	int	ns;
	int	ne;
	Rune*	news;
	Rune*	p;

	n = iend - istart;
	if(n > 0) {
		// replace e->s with e->s[0:istart] + e->s[iend:]
		ns = Strlen(e->s);
		if(istart == 0 && iend == ns)
			e->s = nil;
		else {
			ne = ns- iend;
			news = newstr(istart+ne);
			p = Stradd(news, e->s, istart);
			p = Stradd(p, e->s+iend, ne);
			*p = 0;
			e->s = news;
		}
		if(e->curs > istart) {
			if(e->curs < iend)
				e->curs = istart;
			else
				e->curs = istart + e->curs - iend;
		}
		if(e->left > istart)
			e->left = max(istart - 1, 0);
		entryscroll(e);
	}
}

// Set entry from snarf buffer.
static void
entrysetfromsnarf(Centry* e)
{
	int f;
	int n;
	Rune* s;
	uchar buf[BIGBUFSIZE];

	f = open("/dev/snarf", OREAD);
	if(f >= 0) {
		n = read(f, buf, BIGBUFSIZE);
		if(n > 0) {
			// trim a trailing newline, as a service...
			if(buf[n-1] == '\n')
				n--;
			s = toStr(buf, n, UTF_8);
			entryset((Control*)e, s);
		}
		close(f);
	}
}

// Given e, a Centry with line wrapping,
// return number of wrapped lines, and fill in
//   *pstartlines=line start indices,
//   *ptopline=line# of top displayed line,
//   *pcursline# containing cursor
static int
entrywrapcalc(Centry* e, int** plinestarts, int* ptopline, int* pcursline)
{
	int i, nlines, topline, cursline, i1, i2;
	Rune** lines;
	int* linestarts;

	nlines = wrapstring(fonts[CtlFnt].f, e->s, Dx(e->r)-2*ENTHMARGIN, &lines, &linestarts);
	topline = 0;
	cursline = 0;
	for(i = 0; i < nlines; i++) {
		i1 = linestarts[i];
		i2 = linestarts[i+1];
		if(e->left >= i1 && e->left < i2)
			topline = i;
		if(e->curs >= i1 && e->curs < i2)
			cursline = i;
	}
	if(e->curs == linestarts[nlines])
		cursline = nlines - 1;
	*plinestarts = linestarts;
	*ptopline = topline;
	*pcursline = cursline;
	return nlines;
}

// make sure can see cursor and following char or two, and redraw
static void
entryscroll(Centry* e)
{
	Rune* s;
	int w;
	Font* fnt;
	int wantw;
	int* linestarts;
	int cursline, topline, vislines;

	s = e->s;
	if(e->linewrap) {
		// For multiple line entries, c->left is the char
		// at the beginning of the topmost visible line,
		// and we just want to scroll to make sure that
		// the line with the cursor is visible
		entrywrapcalc(e, &linestarts, &topline, &cursline);
		if(cursline < topline)
			topline = cursline;
		else {
			vislines = (Dy(e->r)-2*ENTVMARGIN)/ctllinespace;
			if(cursline >= topline+vislines)
				topline = cursline-vislines+1;
		}
		e->left = linestarts[topline];
	}
	else {
		if(e->curs < e->left)
			e->left = e->curs;
		else if(e->curs > e->left) {
			fnt = fonts[CtlFnt].f;
			wantw = Dx(e->r) - 2*ENTHMARGIN - 2*ctlspspace;
			while(e->left < e->curs - 1) {
				w = runestringnwidth(fnt, s+e->left, e->curs - e->left);
				if(w < wantw)
					break;
				e->left++;
			}
		}
	}
	drawctl((Control*)e, 1);
}

Lay*
newlay(int targwidth, int just, int margin, Background bg)
{
	Lay*	ans;
	Item*	it;

	ans = (Lay*)emallocz(sizeof(Lay));
	ans->start = newline();
	ans->end = newline();
	ans->start->pos = Pt(margin, margin);
	ans->start->next = ans->end;
	ans->end->prev = ans->start;
	ans->targetwidth = targwidth - 2*margin;
	if(ans->targetwidth < 0)
		ans->targetwidth = 0;
	ans->margin = margin;
	ans->background = bg;
	ans->just = just;
	it = newispacer(ISPnull);
	it->state = IFbrk|IFcleft|IFcright;
	ans->end->items = it;
	return ans;
}

Line*
newline(void)
{
	return (Line*)emallocz(sizeof(Line));
}

Loc*
newloc(void)
{
	Loc* ans;

	ans = (Loc*)emallocz(sizeof(Loc));
	ans->lelen = 10;
	ans->le = (Locelem*)emallocz(ans->lelen * sizeof(Locelem));
	return ans;
}

void
addloc(Loc* loc, int kind, Point pos)
{
	if(loc->n == loc->lelen) {
		loc->lelen += 10;
		loc->le = (Locelem*)erealloc(loc->le, loc->lelen * sizeof(Locelem));
	}
	loc->le[loc->n].kind = kind;
	loc->le[loc->n].pos = pos;
	loc->n++;
}

// return last frame in loc's path
Frame*
lastframe(Loc* loc)
{
	int	i;

	for(i = loc->n - 1; i >= 0; i--)
		if(loc->le[i].kind == LEframe)
			return loc->le[i].frame;
	return nil;
}

void
printloc(Loc* loc, char* msg)
{
	int	i;

	trace("%s: Loc with %d components, pos=(%d,%d)\n", msg, loc->n, loc->pos.x, loc->pos.y);
	for(i = 0; i < loc->n; i++) {
		switch(loc->le[i].kind) {
		case LEframe:
			trace("frame %p\n", (void*)loc->le[i].frame);
			break;
		case LEline:
			trace("line %p\n", (void*)loc->le[i].line);
			break;
		case LEitem:
			trace("item: %p\n%I", (void*)loc->le[i].item, loc->le[i].item);
			break;
		case LEtablecell:
			trace("tablecell: %p, cellid=%d\n", (void*)loc->le[i].tcell, loc->le[i].tcell->cellid);
			break;
		case LEcontrol:
			trace("control %p\n", (void*)loc->le[i].control);
			break;
		}
	}
}

static Sources*
newsources(void)
{
	Sources* ans;

	ans = emallocz(sizeof(Sources));
	return ans;
}

static Source*
newshtml(ByteSource* bs, ItemSource* is)
{
	Shtml* s;

	s = (Shtml*)emallocz(sizeof(Shtml));
	s->tag = Shtmltag;
	s->bs = bs;
	s->itsrc = is;
	return (Source*)s;
}

static Source*
newsimage(ByteSource* bs, CImage* ci, ImageSource* is)
{
	Simage* s;

	s = (Simage*)emallocz(sizeof(Simage));
	s->tag = Simagetag;
	s->bs = bs;
	s->ci = ci;
	s->imsrc = is;
	return (Source*)s;
}

static void
addsource(Sources* srcs, Source* s)
{
	s->next = srcs->srcs;
	srcs->srcs = s;
	srcs->tot++;
}

static Source*
findbs(Sources* srcs, ByteSource* bs)
{
	Source*	s;

	for(s = srcs->srcs; s != nil; s = s->next) {
		if(s->bs == bs)
			return s;
	}
	return nil;
}

// spawned to animate images in frame f = args[0]
static void
animproc(void* arg)
{
USED(arg);
/* TODO
	Frame*	f;
	Itemlist*	aits;
	int	del;
	int	d;
	vlong	tot;
	Loc*	loc;
	Point	p;
	Control*	ctl;
	MaskedImage**	ms;
	Item*	i;
	Item*	it;
	MaskedImage*	m;
	Control*	c;
	int	newdel;
	Itemlist*	al;

	f = (Frame*)args[0];
	f->animpid = pctl(0, nil);
	aits = nil;
	del = 10000000;
	for(i = f->doc->images; i != nil; i = i->nextimage) {
		ms = i->ci->mims;
		if(i->ci->mimslen > 1) {
				loc = findloc(f, ZP, it);
				if(loc == nil) {
					if(dbglay)
						trace("couldn't find item for animated image\n");
					continue;
				}
				p = loc->le[loc->n - 1].pos;
				p.x += i->hspace + i->border;
				ctl = newanimimage(f, i->ci, f->layout->background, 0);
				ctl->r = rectaddpt(ctl->r, p);
				i->ctlid = addcontrol(f, ctl);
				d = ms[0]->delay;
				if(dbglay)
					trace("added anim ctl %d for image %S, initial delay %d\n", i->ctlid, i->ci->src->url->url, d);
				aits = newItempl(it, aits);
				if(d < del)
					del = d;
			}
			break;
		}
	}
	if(aits == nil)
		return ;
	tot = (vlong)0;
	while(1) {
		sleep(del);
		tot = tot + (vlong)del;
		newdel = 10000000;
		for(al = aits; al != nil; al = al->tl) {
			it = al->hd;
			// TODO: declare Item* tmp_32
			tmp_32 = al->hd;
			switch(tmp_32->tag) {
			case Iimagetag:
				i = (Iimage*)tmp_32;
				ms = i->ci->mims;
				// TODO: declare Control* tmp_33
				tmp_33 = f->controls[i->ctlid];
				switch(tmp_33->tag) {
				case Canimimagetag:
					c = (Canimimage*)tmp_33;
					m = ms[c->cur];
					d = m->delay;
					if(d > 0) {
						d = (int)(tot%((vlong)d));
						if(d > 0)
							d = m->delay - d;
					}
					if(d == 0) {
						c->cur++;
						if(c->cur == arraylen(ms))
							c->cur = 0;
						d = ms[c->cur]->delay;
						draw(c, 1);
					}
					if(d < newdel)
						newdel = d;
					break;
				}
				break;
			}
		}
		del = newdel;
	}
*/
}