added shade code skeleton

20 files changed, 423 insertions, 41 deletions

diff --git a/Jamfile b/Jamfile
index ebf69619..8d6e1f29 100644
--- a/Jamfile
+++ b/Jamfile
@@ -71,13 +71,16 @@ Library libfitz :
 	tree/font.c
 	tree/colorspace.c
 	tree/image.c
+	tree/shade.c
 
 	tree/tree.c
 	tree/node1.c
 	tree/node2.c
 	tree/text.c
 	tree/path.c
+
 	tree/debug.c
+	tree/optimize.c
 
 	# render
 	render/glyphcache.c
@@ -87,6 +90,7 @@ Library libfitz :
 	render/fill.c
 	render/stroke.c
 	render/scale.c
+	render/shade.c
 	render/rastport.c
 	render/render.c
 ;
@@ -121,6 +125,7 @@ Library libmupdf :
 	mupdf/image2.c
 	mupdf/xobject.c
 	mupdf/pattern.c
+	mupdf/shade.c
 	mupdf/resources.c
 	mupdf/page.c
 	mupdf/build.c
diff --git a/include/fitz.h b/include/fitz.h
index 2e2c69d1..4aa56011 100644
--- a/include/fitz.h
+++ b/include/fitz.h
@@ -22,6 +22,7 @@
 #include "fitz/pixmap.h"
 #include "fitz/colorspace.h"
 #include "fitz/image.h"
+#include "fitz/shade.h"
 
 #include "fitz/tree.h"
 #include "fitz/path.h"
diff --git a/include/fitz/shade.h b/include/fitz/shade.h
new file mode 100644
index 00000000..7641f609
--- /dev/null
+++ b/include/fitz/shade.h
@@ -0,0 +1,15 @@
+typedef struct fz_shade_s fz_shade;
+
+struct fz_shade_s
+{
+	int refs;
+	fz_colorspace *cs;
+	// ...
+};
+
+fz_shade *fz_keepshade(fz_shade *shade);
+void fz_dropshade(fz_shade *shade);
+
+fz_rect fz_boundshade(fz_shade *shade, fz_matrix ctm);
+fz_error *fz_rendershade(fz_shade *shade, fz_matrix ctm, fz_colorspace *dsts, fz_pixmap *dstp, int over);
+
diff --git a/include/fitz/tree.h b/include/fitz/tree.h
index 57175619..15e4bcf1 100644
--- a/include/fitz/tree.h
+++ b/include/fitz/tree.h
@@ -15,7 +15,12 @@ void fz_droptree(fz_tree *tree);
 
 fz_rect fz_boundtree(fz_tree *tree, fz_matrix ctm);
 void fz_debugtree(fz_tree *tree);
-void fz_insertnode(fz_node *parent, fz_node *child);
+void fz_insertnodefirst(fz_node *parent, fz_node *child);
+void fz_insertnodelast(fz_node *parent, fz_node *child);
+void fz_insertnodeafter(fz_node *prev, fz_node *child);
+void fz_removenode(fz_node *child);
+
+fz_error *fz_optimizetree(fz_tree *tree);
 
 /* node types */
 
@@ -133,6 +138,12 @@ struct fz_imagenode_s
 	fz_image *image;
 };
 
+struct fz_shadenode_s
+{
+	fz_node super;
+	fz_shade *shade;
+};
+
 /* common to all nodes */
 void fz_initnode(fz_node *node, fz_nodekind kind);
 fz_rect fz_boundnode(fz_node *node, fz_matrix ctm);
@@ -155,6 +166,7 @@ int fz_ismetanode(fz_node *node);
 fz_error *fz_newlinknode(fz_node **nodep, fz_tree *subtree);
 fz_error *fz_newcolornode(fz_node **nodep, fz_colorspace *cs, int n, float *v);
 fz_error *fz_newimagenode(fz_node **nodep, fz_image *image);
+fz_error *fz_newshadenode(fz_node **nodep, fz_shade *shade);
 
 int fz_islinknode(fz_node *node);
 int fz_iscolornode(fz_node *node);
diff --git a/include/mupdf/content.h b/include/mupdf/content.h
index f891c3c7..b6eefae9 100644
--- a/include/mupdf/content.h
+++ b/include/mupdf/content.h
@@ -18,7 +18,8 @@ enum
 	PDF_MCOLOR,
 	PDF_MLAB,
 	PDF_MINDEXED,
-	PDF_MPATTERN
+	PDF_MPATTERN,
+	PDF_MSHADE
 };
 
 struct pdf_material_s
@@ -28,6 +29,7 @@ struct pdf_material_s
 	float v[32];
 	pdf_indexed *indexed;
 	pdf_pattern *pattern;
+	fz_shade *shade;
 };
 
 struct pdf_gstate_s
@@ -87,6 +89,7 @@ void pdf_initgstate(pdf_gstate *gs);
 fz_error *pdf_setcolorspace(pdf_csi *csi, int what, fz_colorspace *cs);
 fz_error *pdf_setcolor(pdf_csi *csi, int what, float *v);
 fz_error *pdf_setpattern(pdf_csi *csi, int what, pdf_pattern *pat, float *v);
+fz_error *pdf_setshade(pdf_csi *csi, int what, fz_shade *shade);
 
 fz_error *pdf_buildstrokepath(pdf_gstate *gs, fz_pathnode *path);
 fz_error *pdf_buildfillpath(pdf_gstate *gs, fz_pathnode *path, int evenodd);
diff --git a/include/mupdf/rsrc.h b/include/mupdf/rsrc.h
index 91deb38d..371661a0 100644
--- a/include/mupdf/rsrc.h
+++ b/include/mupdf/rsrc.h
@@ -66,6 +66,8 @@ struct pdf_pattern_s
 fz_error *pdf_loadpattern(pdf_pattern **patp, pdf_xref *xref, fz_obj *obj, fz_obj *ref);
 void pdf_droppattern(pdf_pattern *pat);
 
+fz_error *pdf_loadshade(fz_shade **shadep, pdf_xref *xref, fz_obj *obj, fz_obj *ref);
+
 /*
  * XObject
  */
diff --git a/include/mupdf/xref.h b/include/mupdf/xref.h
index e189ba6a..f1cf79c0 100644
--- a/include/mupdf/xref.h
+++ b/include/mupdf/xref.h
@@ -24,6 +24,7 @@ struct pdf_xref_s
 	pdf_rsrc *rimage;
 	pdf_rsrc *rxobject;
 	pdf_rsrc *rpattern;
+	pdf_rsrc *rshade;
 	pdf_rsrc *rcolorspace;
 };
 
diff --git a/mupdf/build.c b/mupdf/build.c
index 3b65ff6a..541bf056 100644
--- a/mupdf/build.c
+++ b/mupdf/build.c
@@ -140,6 +140,27 @@ pdf_setpattern(pdf_csi *csi, int what, pdf_pattern *pat, float *v)
 }
 
 fz_error *
+pdf_setshade(pdf_csi *csi, int what, fz_shade *shade)
+{
+	pdf_gstate *gs = csi->gstate + csi->gtop;
+	fz_error *error;
+	pdf_material *mat;
+
+	error = pdf_flushtext(csi);
+	if (error)
+		return error;
+
+printf("setshade!\n");
+
+	mat = what == PDF_MFILL ? &gs->fill : &gs->stroke;
+
+	mat->kind = PDF_MSHADE;
+	mat->shade = shade;
+
+	return nil;
+}
+
+fz_error *
 pdf_buildstrokepath(pdf_gstate *gs, fz_pathnode *path)
 {
 	fz_error *error;
@@ -188,9 +209,31 @@ addcolorshape(pdf_gstate *gs, fz_node *shape, fz_colorspace *cs, float *v)
 	error = fz_newcolornode(&solid, cs, cs->n, v);
 	if (error) return error;
 
-	fz_insertnode(mask, shape);
-	fz_insertnode(mask, solid);
-	fz_insertnode(gs->head, mask);
+	fz_insertnodelast(mask, shape);
+	fz_insertnodelast(mask, solid);
+	fz_insertnodelast(gs->head, mask);
+
+	return nil;
+}
+
+static fz_error *
+addshadeshape(pdf_gstate *gs, fz_node *shape, fz_shade *shade)
+{
+	fz_error *error;
+	fz_node *mask;
+	fz_node *color;
+
+printf("addshade!\n");
+
+	error = fz_newmasknode(&mask);
+	if (error) return error;
+
+	error = fz_newshadenode(&color, shade);
+	if (error) return error;
+
+	fz_insertnodelast(mask, shape);
+	fz_insertnodelast(mask, color);
+	fz_insertnodelast(gs->head, mask);
 
 	return nil;
 }
@@ -210,9 +253,9 @@ addinvisibleshape(pdf_gstate *gs, fz_node *shape)
 	error = fz_endpath(path, FZ_FILL, nil, nil);
 	if (error) return error;
 
-	fz_insertnode(mask, (fz_node*)path);
-	fz_insertnode(mask, shape);
-	fz_insertnode(gs->head, mask);
+	fz_insertnodelast(mask, (fz_node*)path);
+	fz_insertnodelast(mask, shape);
+	fz_insertnodelast(gs->head, mask);
 
 	return nil;
 }
@@ -260,9 +303,9 @@ addpatternshape(pdf_gstate *gs, fz_node *shape,
 	error = fz_newovernode(&over);
 	if (error) return error;
 
-	fz_insertnode(mask, shape);
-	fz_insertnode(mask, xform);
-	fz_insertnode(xform, over);
+	fz_insertnodelast(mask, shape);
+	fz_insertnodelast(mask, xform);
+	fz_insertnodelast(xform, over);
 
 	/* get bbox of shape in pattern space for stamping */
 	ptm = fz_concat(ctm, fz_invertmatrix(pat->matrix));
@@ -295,15 +338,15 @@ printf("  %d,%d to %d,%d\n", x0, y0, x1, y1);
 			if (error) return error;
 			error = fz_newlinknode(&link, pat->tree);
 			if (error) return error;
-			fz_insertnode(xform, link);
-			fz_insertnode(over, xform);
+			fz_insertnodelast(xform, link);
+			fz_insertnodelast(over, xform);
 		}
 	}
 
 	if (pat->ismask)
 		return addcolorshape(gs, mask, cs, v);
 
-	fz_insertnode(gs->head, mask);
+	fz_insertnodelast(gs->head, mask);
 	return nil;
 }
 
@@ -313,7 +356,7 @@ pdf_addfillshape(pdf_gstate *gs, fz_node *shape)
 	switch (gs->fill.kind)
 	{
 	case PDF_MNONE:
-		fz_insertnode(gs->head, shape);
+		fz_insertnodelast(gs->head, shape);
 		return nil;
 	case PDF_MCOLOR:
 	case PDF_MLAB:
@@ -321,6 +364,8 @@ pdf_addfillshape(pdf_gstate *gs, fz_node *shape)
 		return addcolorshape(gs, shape, gs->fill.cs, gs->fill.v);
 	case PDF_MPATTERN:
 		return addpatternshape(gs, shape, gs->fill.pattern, gs->fill.cs, gs->fill.v);
+	case PDF_MSHADE:
+		return addshadeshape(gs, shape, gs->fill.shade);
 	default:
 		return fz_throw("unimplemented material");
 	}
@@ -332,7 +377,7 @@ pdf_addstrokeshape(pdf_gstate *gs, fz_node *shape)
 	switch (gs->stroke.kind)
 	{
 	case PDF_MNONE:
-		fz_insertnode(gs->head, shape);
+		fz_insertnodelast(gs->head, shape);
 		return nil;
 	case PDF_MCOLOR:
 	case PDF_MLAB:
@@ -340,6 +385,8 @@ pdf_addstrokeshape(pdf_gstate *gs, fz_node *shape)
 		return addcolorshape(gs, shape, gs->stroke.cs, gs->stroke.v);
 	case PDF_MPATTERN:
 		return addpatternshape(gs, shape, gs->stroke.pattern, gs->stroke.cs, gs->stroke.v);
+	case PDF_MSHADE:
+		return addshadeshape(gs, shape, gs->stroke.shade);
 	default:
 		return fz_throw("unimplemented material");
 	}
@@ -358,9 +405,9 @@ pdf_addclipmask(pdf_gstate *gs, fz_node *shape)
 	error = fz_newovernode(&over);
 	if (error) return error;
 
-	fz_insertnode(mask, shape);
-	fz_insertnode(mask, over);
-	fz_insertnode(gs->head, mask);
+	fz_insertnodelast(mask, shape);
+	fz_insertnodelast(mask, over);
+	fz_insertnodelast(gs->head, mask);
 	gs->head = over;
 
 	return nil;
@@ -375,8 +422,8 @@ pdf_addtransform(pdf_gstate *gs, fz_node *transform)
 	error = fz_newovernode(&over);
 	if (error) return error;
 
-	fz_insertnode(gs->head, transform);
-	fz_insertnode(transform, over);
+	fz_insertnodelast(gs->head, transform);
+	fz_insertnodelast(transform, over);
 	gs->head = over;
 
 	return nil;
@@ -410,13 +457,13 @@ pdf_showimage(pdf_csi *csi, pdf_image *img)
 			if (error) return error;
 			error = fz_newmasknode(&mask);
 			if (error) return error;
-			fz_insertnode(mask, shape);
-			fz_insertnode(mask, color);
-			fz_insertnode(csi->gstate[csi->gtop].head, mask);
+			fz_insertnodelast(mask, shape);
+			fz_insertnodelast(mask, color);
+			fz_insertnodelast(csi->gstate[csi->gtop].head, mask);
 		}
 		else
 		{
-			fz_insertnode(csi->gstate[csi->gtop].head, color);
+			fz_insertnodelast(csi->gstate[csi->gtop].head, color);
 		}
 	}
 
@@ -521,7 +568,7 @@ pdf_flushtext(pdf_csi *csi)
 				if (error)
 					return error;
 			}
-			fz_insertnode(csi->textclip, (fz_node*)csi->text);
+			fz_insertnodelast(csi->textclip, (fz_node*)csi->text);
 			break;
 		}
 
diff --git a/mupdf/interpret.c b/mupdf/interpret.c
index c0a9b882..22ed7f20 100644
--- a/mupdf/interpret.c
+++ b/mupdf/interpret.c
@@ -255,7 +255,7 @@ runkeyword(pdf_csi *csi, pdf_xref *xref, fz_obj *rdb, char *buf)
 				goto syntaxerror;
 			error = fz_newmetanode(&meta, csi->stack[0], nil);
 			if (error) return error;
-			fz_insertnode(gstate->head, meta);
+			fz_insertnodelast(gstate->head, meta);
 		}
 
 		else if (!strcmp(buf, "DP"))
@@ -265,7 +265,7 @@ runkeyword(pdf_csi *csi, pdf_xref *xref, fz_obj *rdb, char *buf)
 				goto syntaxerror;
 			error = fz_newmetanode(&meta, csi->stack[0], csi->stack[1]);
 			if (error) return error;
-			fz_insertnode(gstate->head, meta);
+			fz_insertnodelast(gstate->head, meta);
 		}
 
 		else if (!strcmp(buf, "BMC"))
@@ -275,7 +275,7 @@ runkeyword(pdf_csi *csi, pdf_xref *xref, fz_obj *rdb, char *buf)
 				goto syntaxerror;
 			error = fz_newmetanode(&meta, csi->stack[0], nil);
 			if (error) return error;
-			fz_insertnode(gstate->head, meta);
+			fz_insertnodelast(gstate->head, meta);
 		}
 
 		else if (!strcmp(buf, "BDC"))
@@ -285,7 +285,7 @@ runkeyword(pdf_csi *csi, pdf_xref *xref, fz_obj *rdb, char *buf)
 				goto syntaxerror;
 			error = fz_newmetanode(&meta, csi->stack[0], csi->stack[1]);
 			if (error) return error;
-			fz_insertnode(gstate->head, meta);
+			fz_insertnodelast(gstate->head, meta);
 		}
 
 		else if (!strcmp(buf, "EMC"))
@@ -456,6 +456,7 @@ Lsetcolorspace:
 		{
 			pdf_material *mat;
 			pdf_pattern *pat;
+			fz_shade *shd;
 			fz_obj *dict;
 			fz_obj *obj;
 
@@ -503,12 +504,26 @@ Lsetcolor:
 					return fz_throw("syntaxerror: missing pattern resource");
 
 				pat = pdf_findresource(xref->rpattern, obj);
-				if (!pat)
+				if (pat)
+				{
+					error = pdf_setpattern(csi, what, pat, csi->top == 1 ? nil : v);
+					if (error) return error;
+				}
+
+				shd = pdf_findresource(xref->rshade, obj);
+				if (shd)
+				{
+					error = pdf_setshade(csi, what, shd);
+					if (error) return error;
+				}
+
+				if (!pat && !shd)
 					return fz_throw("syntaxerror: missing pattern resource");
 
-				error = pdf_setpattern(csi, what, pat, csi->top == 1 ? nil : v);
-				if (error) return error;
 				break;
+
+			case PDF_MSHADE:
+				return fz_throw("syntaxerror: cannot set color in shade objects");
 			}
 		}
 
@@ -740,6 +755,31 @@ fz_debugobj(rdb);
 			}
 		}
 
+		else if (!strcmp(buf, "sh"))
+		{
+			fz_obj *dict;
+			fz_obj *obj;
+			fz_shade *shd;
+			fz_node *node;
+
+			dict = fz_dictgets(rdb, "Pattern");
+			if (!dict)
+				return fz_throw("syntaxerror: missing pattern resource");
+
+			obj = fz_dictget(dict, csi->stack[csi->top - 1]);
+			if (!obj)
+				return fz_throw("syntaxerror: missing pattern resource");
+
+			shd = pdf_findresource(xref->rshade, obj);
+			if (!shd)
+				return fz_throw("syntaxerror: missing pattern resource");
+
+			error = fz_newshadenode(&node, shd);
+			if (error) return error;
+
+			fz_insertnodelast(gstate->head, node);
+		}
+
 		else if (!strcmp(buf, "d0"))
 		{
 			fz_warn("unimplemented: d0 charprocs");
diff --git a/mupdf/page.c b/mupdf/page.c
index 11ab6727..8ae29541 100644
--- a/mupdf/page.c
+++ b/mupdf/page.c
@@ -127,6 +127,12 @@ pdf_loadpage(pdf_page **pagep, pdf_xref *xref, fz_obj *dict)
 		return error;
 	}
 
+	error = fz_optimizetree(tree);
+	if (error) {
+		fz_dropobj(rdb);
+		return error;
+	}
+
 	/*
 	 * Create page object
 	 */
diff --git a/mupdf/resources.c b/mupdf/resources.c
index 08434c0b..dbf15a7c 100644
--- a/mupdf/resources.c
+++ b/mupdf/resources.c
@@ -96,10 +96,8 @@ preloadpattern(pdf_xref *xref, fz_obj *ref)
 
 	if (pdf_findresource(xref->rpattern, ref))
 		return nil;
-/*
-	if (pdf_findresource(xref->rshading, ref))
+	if (pdf_findresource(xref->rshade, ref))
 		return nil;
-*/
 
 	rsrc = fz_malloc(sizeof(pdf_rsrc));
 	if (!rsrc)
@@ -128,10 +126,15 @@ preloadpattern(pdf_xref *xref, fz_obj *ref)
 
 	else if (fz_toint(type) == 2)
 	{
-		/* load shading */
+		error = pdf_loadshade((fz_shade**)&rsrc->val, xref, obj, ref);
 		fz_dropobj(obj);
-		fz_free(rsrc);
-		return fz_throw("jeong was not here...");
+		if (error) {
+			fz_free(rsrc);
+			return error;
+		}
+		rsrc->next = xref->rshade;
+		xref->rshade = rsrc;
+		return nil;
 	}
 
 	else
diff --git a/mupdf/shade.c b/mupdf/shade.c
new file mode 100644
index 00000000..762e3897
--- /dev/null
+++ b/mupdf/shade.c
@@ -0,0 +1,24 @@
+#include <fitz.h>
+#include <mupdf.h>
+
+fz_error *
+pdf_loadshade(fz_shade **shadep, pdf_xref *xref, fz_obj *obj, fz_obj *ref)
+{
+	fz_error *error;
+	fz_shade *shade;
+
+	shade = fz_malloc(sizeof(fz_shade));
+	if (!shade)
+		return fz_outofmem;
+
+printf("loading shade pattern\n");
+
+	// ...
+
+	*shadep = shade;
+	return nil;
+
+cleanup:
+	return error;
+}
+
diff --git a/mupdf/type3.c b/mupdf/type3.c
index 082f4ce8..59c82db2 100644
--- a/mupdf/type3.c
+++ b/mupdf/type3.c
@@ -281,6 +281,10 @@ printf("  bbox [%g %g %g %g]\n", bbox.min.x,bbox.min.y,bbox.max.x,bbox.max.y);
 				error = loadcharproc(&font->charprocs[i], xref, resources, obj);
 				if (error)
 					goto cleanup2;
+
+				error = fz_optimizetree(font->charprocs[i]);
+				if (error)
+					goto cleanup2;
 			}
 		}
 	}
diff --git a/render/render.c b/render/render.c
index b92c8fe0..58e4b6f0 100644
--- a/render/render.c
+++ b/render/render.c
@@ -1,6 +1,7 @@
 #include <fitz.h>
 
-#define DEBUG(args...) printf(args)
+#define noDEBUG(args...) printf(args)
+#define DEBUG(args...)
 
 #define FNONE 0
 #define FOVER 1
@@ -533,6 +534,31 @@ cleanup:
 }
 
 /*
+ * Shade
+ */
+
+static fz_error *
+rendershade(fz_renderer *gc, fz_shadenode *node, fz_matrix ctm)
+{
+	fz_error *error;
+	fz_irect bbox;
+
+	assert(!gc->maskonly);
+
+	if (gc->flag & FOVER)
+		return fz_rendershade(node->shade, ctm, gc->model, gc->over, 1);
+
+	bbox = fz_roundrect(fz_boundnode((fz_node*)node, ctm));
+	bbox = fz_intersectirects(gc->clip, bbox);
+
+	error = fz_newpixmapwithrect(&gc->dest, bbox, gc->model->n + 1);
+	if (error)
+		return error;
+
+	return fz_rendershade(node->shade, ctm, gc->model, gc->dest, 0);
+}
+
+/*
  * Over, Mask and Blend
  */
 
@@ -820,6 +846,8 @@ rendernode(fz_renderer *gc, fz_node *node, fz_matrix ctm)
 		return rendertext(gc, (fz_textnode*)node, ctm);
 	case FZ_NIMAGE:
 		return renderimage(gc, (fz_imagenode*)node, ctm);
+	case FZ_NSHADE:
+		return rendershade(gc, (fz_shadenode*)node, ctm);
 	case FZ_NLINK:
 		return rendernode(gc, ((fz_linknode*)node)->tree->root, ctm);
 	case FZ_NMETA:
diff --git a/tree/debug.c b/tree/debug.c
index 0f4edada..a61872c4 100644
--- a/tree/debug.c
+++ b/tree/debug.c
@@ -155,6 +155,12 @@ static void lispimage(fz_imagenode *node, int level)
 	printf("(image)\n");
 }
 
+static void lispshade(fz_shadenode *node, int level)
+{
+	indent(level);
+	printf("(shade)\n");
+}
+
 static void lispnode(fz_node *node, int level)
 {
 	if (!node)
@@ -175,6 +181,7 @@ static void lispnode(fz_node *node, int level)
 	case FZ_NPATH: lisppath((fz_pathnode*)node, level); break;
 	case FZ_NTEXT: lisptext((fz_textnode*)node, level); break;
 	case FZ_NIMAGE: lispimage((fz_imagenode*)node, level); break;
+	case FZ_NSHADE: lispshade((fz_shadenode*)node, level); break;
 	case FZ_NLINK: lisplink((fz_linknode*)node, level); break;
 	}
 }
diff --git a/tree/node1.c b/tree/node1.c
index 2587077c..c2d6e876 100644
--- a/tree/node1.c
+++ b/tree/node1.c
@@ -5,6 +5,7 @@ void fz_droplinknode(fz_linknode* node);
 void fz_droppathnode(fz_pathnode* node);
 void fz_droptextnode(fz_textnode* node);
 void fz_dropimagenode(fz_imagenode* node);
+void fz_dropshadenode(fz_shadenode* node);
 
 fz_rect fz_boundtransformnode(fz_transformnode* node, fz_matrix ctm);
 fz_rect fz_boundovernode(fz_overnode* node, fz_matrix ctm);
@@ -53,6 +54,9 @@ fz_dropnode(fz_node *node)
 	case FZ_NIMAGE:
 		fz_dropimagenode((fz_imagenode *) node);
 		break;
+	case FZ_NSHADE:
+		fz_dropshadenode((fz_shadenode *) node);
+		break;
 	case FZ_NLINK:
 		fz_droplinknode((fz_linknode *) node);
 		break;
@@ -85,6 +89,8 @@ fz_boundnode(fz_node *node, fz_matrix ctm)
 		return fz_boundtextnode((fz_textnode *) node, ctm);
 	case FZ_NIMAGE:
 		return fz_boundimagenode((fz_imagenode *) node, ctm);
+	case FZ_NSHADE:
+		return fz_boundshadenode((fz_shadenode *) node, ctm);
 	case FZ_NLINK:
 		return fz_boundlinknode((fz_linknode *) node, ctm);
 	case FZ_NMETA:
diff --git a/tree/node2.c b/tree/node2.c
index 5c3e3931..ceb59ad6 100644
--- a/tree/node2.c
+++ b/tree/node2.c
@@ -274,3 +274,35 @@ fz_boundimagenode(fz_imagenode *node, fz_matrix ctm)
 	return fz_transformaabb(ctm, bbox);
 }
 
+/*
+ * Shade node
+ */
+
+fz_error *
+fz_newshadenode(fz_node **nodep, fz_shade *shade)
+{
+	fz_shadenode *node;
+
+	node = fz_malloc(sizeof (fz_shadenode));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NSHADE);
+	node->shade = shade;
+
+	return nil;
+}
+
+void
+fz_dropshadenode(fz_shadenode *node)
+{
+	fz_dropshade(node->shade);
+}
+
+fz_rect
+fz_boundshadenode(fz_shadenode *node, fz_matrix ctm)
+{
+	return fz_boundshade(node->shade, ctm);
+}
+
diff --git a/tree/optimize.c b/tree/optimize.c
new file mode 100644
index 00000000..14d98232
--- /dev/null
+++ b/tree/optimize.c
@@ -0,0 +1,56 @@
+#include <fitz.h>
+
+/*
+ * Remove useless overs that only have one child.
+ */
+
+static void cleanovers(fz_node *node)
+{
+	fz_node *prev;
+	fz_node *over;
+	fz_node *child;
+
+	prev = nil;
+	for (over = node->first; over; over = prev->next)
+	{
+		cleanovers(over);
+
+		if (fz_isovernode(over))
+		{
+			if (over->first == over->last)
+			{
+				printf("  remove unused over node\n");
+				child = over->first;
+				fz_removenode(over);
+				if (child)
+				{
+					if (prev)
+						fz_insertnodeafter(prev, child);
+					else
+						fz_insertnodefirst(node, child);
+				}
+				over = nil;
+			}
+		}
+
+		if (over)
+			prev = over;
+	}
+}
+
+fz_error *
+fz_optimizetree(fz_tree *tree)
+{
+	printf("optimizing tree\n");
+
+//printf("before:\n");
+//fz_debugtree(tree);
+
+	cleanovers(tree->root);
+
+//printf("after:\n");
+//fz_debugtree(tree);
+
+	return nil;
+}
+
diff --git a/tree/shade.c b/tree/shade.c
new file mode 100644
index 00000000..cb33072e
--- /dev/null
+++ b/tree/shade.c
@@ -0,0 +1,26 @@
+#include <fitz.h>
+
+fz_shade *
+fz_keepshade(fz_shade *shade)
+{
+	shade->refs ++;
+	return shade;
+}
+
+void
+fz_dropshade(fz_shade *shade)
+{
+	if (--shade->refs == 0)
+	{
+		if (shade->cs)
+			fz_dropcolorspace(shade->cs);
+		fz_free(shade);
+	}
+}
+
+fz_rect
+fz_boundshade(fz_shade *shade, fz_matrix ctm)
+{
+	return fz_infiniterect;
+}
+
diff --git a/tree/tree.c b/tree/tree.c
index f07e564f..e59d0413 100644
--- a/tree/tree.c
+++ b/tree/tree.c
@@ -43,7 +43,23 @@ fz_boundtree(fz_tree *tree, fz_matrix ctm)
 }
 
 void
-fz_insertnode(fz_node *parent, fz_node *child)
+fz_insertnodefirst(fz_node *parent, fz_node *child)
+{
+	assert(fz_istransformnode(parent) ||
+		fz_isovernode(parent) ||
+		fz_ismasknode(parent) ||
+		fz_isblendnode(parent) ||
+		fz_ismetanode(parent));
+
+	child->parent = parent;
+	child->next = parent->first;
+	parent->first = child;
+	if (!parent->last)
+		parent->last = child;
+}
+
+void
+fz_insertnodelast(fz_node *parent, fz_node *child)
 {
 	assert(fz_istransformnode(parent) ||
 		fz_isovernode(parent) ||
@@ -59,3 +75,51 @@ fz_insertnode(fz_node *parent, fz_node *child)
 	parent->last = child;
 }
 
+void
+fz_insertnodeafter(fz_node *prev, fz_node *child)
+{
+	fz_node *parent = prev->parent;
+
+	assert(fz_istransformnode(parent) ||
+		fz_isovernode(parent) ||
+		fz_ismasknode(parent) ||
+		fz_isblendnode(parent) ||
+		fz_ismetanode(parent));
+
+	child->parent = parent;
+
+	if (parent->last == prev)
+		parent->last = child;
+
+	child->next = prev->next;
+	prev->next = child;
+}
+
+void
+fz_removenode(fz_node *child)
+{
+	fz_node *parent = child->parent;
+	fz_node *prev;
+	fz_node *node;
+
+	if (parent->first == child)
+	{
+		parent->first = child->next;
+	}
+
+	prev = parent->first;
+	node = prev->next;
+
+	while (node)
+	{
+		if (node == child)
+		{
+			prev->next = child->next;
+		}
+		prev = node;
+		node = node->next;
+	}
+
+	parent->last = prev;
+}
+