pdf: structured text and hyperlink support

21 files changed, 2617 insertions, 30 deletions

diff --git a/doc/public/cairo-docs.xml b/doc/public/cairo-docs.xml
index d54e63be6..73c9813f3 100644
--- a/doc/public/cairo-docs.xml
+++ b/doc/public/cairo-docs.xml
@@ -18,6 +18,7 @@
     <xi:include href="xml/cairo-transforms.xml"/>
     <xi:include href="xml/cairo-text.xml"/>
     <xi:include href="xml/cairo-raster-source.xml"/>
+    <xi:include href="xml/cairo-tag.xml"/>
   </chapter>
   <chapter id="cairo-fonts">
     <title>Fonts</title>
diff --git a/doc/public/cairo-sections.txt b/doc/public/cairo-sections.txt
index 4beaa0ae2..fdffc033f 100644
--- a/doc/public/cairo-sections.txt
+++ b/doc/public/cairo-sections.txt
@@ -408,6 +408,14 @@ cairo_raster_source_finish_func_t
 </SECTION>
 
 <SECTION>
+<FILE>cairo-tag</FILE>
+CAIRO_TAG_DEST
+CAIRO_TAG_LINK
+cairo_tag_begin
+cairo_tag_end
+</SECTION>
+
+<SECTION>
 <FILE>cairo-matrix</FILE>
 cairo_matrix_t
 cairo_matrix_init
diff --git a/src/Makefile.sources b/src/Makefile.sources
index fac24d79d..b368f2774 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -279,8 +279,8 @@ _cairo_deflate_stream_sources = cairo-deflate-stream.c
 cairo_sources += $(_cairo_deflate_stream_sources)
 
 cairo_pdf_headers = cairo-pdf.h
-cairo_pdf_private = cairo-pdf-surface-private.h
-cairo_pdf_sources = cairo-pdf-surface.c
+cairo_pdf_private = cairo-pdf-surface-private.h cairo-tag-stack-private.h cairo-tag-attributes-private.h
+cairo_pdf_sources = cairo-pdf-surface.c cairo-pdf-interchange.c cairo-tag-stack.c cairo-tag-attributes.c
 
 cairo_svg_headers = cairo-svg.h
 cairo_svg_private = cairo-svg-surface-private.h
diff --git a/src/cairo-device.c b/src/cairo-device.c
index bacf93b3d..73e5040df 100644
--- a/src/cairo-device.c
+++ b/src/cairo-device.c
@@ -162,6 +162,7 @@ _cairo_device_create_in_error (cairo_status_t status)
     case CAIRO_STATUS_PNG_ERROR:
     case CAIRO_STATUS_FREETYPE_ERROR:
     case CAIRO_STATUS_WIN32_GDI_ERROR:
+    case CAIRO_STATUS_TAG_ERROR:
     default:
 	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 	return (cairo_device_t *) &_nil_device;
diff --git a/src/cairo-error-private.h b/src/cairo-error-private.h
index 25dac7d63..1ab57ddf8 100644
--- a/src/cairo-error-private.h
+++ b/src/cairo-error-private.h
@@ -97,6 +97,7 @@ enum _cairo_int_status {
     CAIRO_INT_STATUS_PNG_ERROR,
     CAIRO_INT_STATUS_FREETYPE_ERROR,
     CAIRO_INT_STATUS_WIN32_GDI_ERROR,
+    CAIRO_INT_STATUS_TAG_ERROR,
 
     CAIRO_INT_STATUS_LAST_STATUS,
 
diff --git a/src/cairo-misc.c b/src/cairo-misc.c
index 35025ad87..e9b0ab6be 100644
--- a/src/cairo-misc.c
+++ b/src/cairo-misc.c
@@ -164,6 +164,8 @@ cairo_status_to_string (cairo_status_t status)
 	return "error occurred in libfreetype";
     case CAIRO_STATUS_WIN32_GDI_ERROR:
 	return "error occurred in the Windows Graphics Device Interface";
+    case CAIRO_STATUS_TAG_ERROR:
+	return "invalid tag name, attributes, or nesting";
     default:
     case CAIRO_STATUS_LAST_STATUS:
 	return "<unknown error status>";
diff --git a/src/cairo-pdf-interchange.c b/src/cairo-pdf-interchange.c
new file mode 100644
index 000000000..95c8ba67f
--- /dev/null
+++ b/src/cairo-pdf-interchange.c
@@ -0,0 +1,993 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2016 Adrian Johnson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Adrian Johnson.
+ *
+ * Contributor(s):
+ *	Adrian Johnson <ajohnson@redneon.com>
+ */
+
+
+/* PDF Document Interchange features:
+ *  - metadata
+ *  - document outline
+ *  - tagged pdf
+ *  - hyperlinks
+ *  - page labels
+ */
+
+#include "cairoint.h"
+
+#include "cairo-pdf.h"
+#include "cairo-pdf-surface-private.h"
+
+#include "cairo-array-private.h"
+#include "cairo-error-private.h"
+#include "cairo-output-stream-private.h"
+
+static void
+write_rect_to_pdf_quad_points (cairo_output_stream_t   *stream,
+			       const cairo_rectangle_t *rect,
+			       double                   surface_height)
+{
+    _cairo_output_stream_printf (stream,
+				 "%f %f %f %f %f %f %f %f",
+				 rect->x,
+				 surface_height - rect->y,
+				 rect->x + rect->width,
+				 surface_height - rect->y,
+				 rect->x + rect->width,
+				 surface_height - (rect->y + rect->height),
+				 rect->x,
+				 surface_height - (rect->y + rect->height));
+}
+
+static void
+write_rect_int_to_pdf_bbox (cairo_output_stream_t       *stream,
+			    const cairo_rectangle_int_t *rect,
+			    double                       surface_height)
+{
+    _cairo_output_stream_printf (stream,
+				 "%d %f %d %f",
+				 rect->x,
+				 surface_height - (rect->y + rect->height),
+				 rect->x + rect->width,
+				 surface_height - rect->y);
+}
+
+static cairo_int_status_t
+add_tree_node (cairo_pdf_surface_t           *surface,
+	       cairo_pdf_struct_tree_node_t  *parent,
+	       const char                    *name,
+	       cairo_pdf_struct_tree_node_t **new_node)
+{
+    cairo_pdf_struct_tree_node_t *node;
+
+    node = malloc (sizeof(cairo_pdf_struct_tree_node_t));
+    if (unlikely (node == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    node->name = strdup (name);
+    node->res = _cairo_pdf_surface_new_object (surface);
+    if (node->res.id == 0)
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    node->parent = parent;
+    cairo_list_init (&node->children);
+    _cairo_array_init (&node->mcid, sizeof(struct page_mcid));
+    memset (&node->annot, 0, sizeof(node->annot));
+    cairo_list_init (&node->children);
+
+    cairo_list_add_tail (&node->link, &parent->children);
+
+    *new_node = node;
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_bool_t
+is_leaf_node (cairo_pdf_struct_tree_node_t *node)
+{
+    return node->parent && cairo_list_is_empty (&node->children) ;
+}
+
+static void
+free_node (cairo_pdf_struct_tree_node_t *node)
+{
+    cairo_pdf_struct_tree_node_t *child, *next;
+
+    if (!node)
+	return;
+
+    cairo_list_foreach_entry_safe (child, next, cairo_pdf_struct_tree_node_t,
+				   &node->children, link)
+    {
+	cairo_list_del (&child->link);
+	free_node (child);
+    }
+    free (node->name);
+    _cairo_array_fini (&node->mcid);
+    free (node);
+}
+
+static cairo_status_t
+add_mcid_to_node (cairo_pdf_surface_t          *surface,
+		  cairo_pdf_struct_tree_node_t *node,
+		  int                           page,
+		  int                          *mcid)
+{
+    struct page_mcid mcid_elem;
+    cairo_int_status_t status;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    status = _cairo_array_append (&ic->mcid_to_tree, &node);
+    if (unlikely (status))
+	return status;
+
+    mcid_elem.page = page;
+    mcid_elem.mcid = _cairo_array_num_elements (&ic->mcid_to_tree) - 1;
+    *mcid = mcid_elem.mcid;
+    return _cairo_array_append (&node->mcid, &mcid_elem);
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_node_object (cairo_pdf_surface_t            *surface,
+					 cairo_pdf_struct_tree_node_t   *node)
+{
+    struct page_mcid *mcid_elem;
+    int i, num_mcid, first_page;
+    cairo_pdf_resource_t *page_res;
+    cairo_pdf_struct_tree_node_t *child;
+
+    _cairo_pdf_surface_update_object (surface, node->res);
+    _cairo_output_stream_printf (surface->output,
+				 "%d 0 obj\n"
+				 "<< /Type /StructElem\n"
+				 "   /S /%s\n"
+				 "   /P %d 0 R\n",
+				 node->res.id,
+				 node->name,
+				 node->parent->res.id);
+
+    if (! cairo_list_is_empty (&node->children)) {
+	if (cairo_list_is_singular (&node->children)) {
+	    child = cairo_list_first_entry (&node->children, cairo_pdf_struct_tree_node_t, link);
+	    _cairo_output_stream_printf (surface->output, "   /K %d 0 R\n", child->res.id);
+	} else {
+	    _cairo_output_stream_printf (surface->output, "   /K [ ");
+
+	    cairo_list_foreach_entry (child, cairo_pdf_struct_tree_node_t,
+				      &node->children, link)
+	    {
+		_cairo_output_stream_printf (surface->output, "%d 0 R ", child->res.id);
+	    }
+	    _cairo_output_stream_printf (surface->output, "]\n");
+	}
+    } else {
+	num_mcid = _cairo_array_num_elements (&node->mcid);
+	if (num_mcid > 0 ) {
+	    mcid_elem = _cairo_array_index (&node->mcid, 0);
+	    first_page = mcid_elem->page;
+	    page_res = _cairo_array_index (&surface->pages, first_page - 1);
+	    _cairo_output_stream_printf (surface->output, "   /Pg %d 0 R\n", page_res->id);
+
+	    if (num_mcid == 1 && node->annot.res.id == 0) {
+		_cairo_output_stream_printf (surface->output, "   /K %d\n", mcid_elem->mcid);
+	    } else {
+		_cairo_output_stream_printf (surface->output, "   /K [ ");
+		if (node->annot.res.id != 0) {
+		    _cairo_output_stream_printf (surface->output,
+						 "%d 0 R ",
+						 node->annot.res.id);
+		}
+		for (i = 0; i < num_mcid; i++) {
+		    mcid_elem = _cairo_array_index (&node->mcid, i);
+		    page_res = _cairo_array_index (&surface->pages, mcid_elem->page - 1);
+		    if (mcid_elem->page == first_page) {
+			_cairo_output_stream_printf (surface->output, "%d ", mcid_elem->mcid);
+		    } else {
+			_cairo_output_stream_printf (surface->output,
+						     "\n       << /Type /MCR /Pg %d 0 R /MCID %d >> ",
+						     page_res->id,
+						     mcid_elem->mcid);
+		    }
+		}
+		_cairo_output_stream_printf (surface->output, "]\n");
+	    }
+	}
+    }
+    _cairo_output_stream_printf (surface->output,
+				 ">>\n"
+				 "endobj\n");
+
+    return _cairo_output_stream_get_status (surface->output);
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_annot (cairo_pdf_surface_t            *surface,
+				   cairo_pdf_struct_tree_node_t   *node)
+{
+    cairo_pdf_resource_t res;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    int sp;
+    char *dest = NULL;
+    int i, num_rects, num_mcid;
+    struct page_mcid *mcid_elem;
+
+    num_mcid = _cairo_array_num_elements (&node->mcid);
+    if (num_mcid == 0 )
+	return status;
+
+    mcid_elem = _cairo_array_index (&node->mcid, 0);
+    if (mcid_elem->page != ic->annot_page)
+	return status;
+
+    num_rects = _cairo_array_num_elements (&node->annot.link_attrs.rects);
+    if (strcmp (node->name, CAIRO_TAG_LINK) == 0 &&
+	node->annot.link_attrs.link_type != TAG_LINK_EMPTY &&
+	(node->annot.extents.valid || num_rects > 0))
+    {
+	res = _cairo_pdf_surface_new_object (surface);
+
+	status = _cairo_array_append (&ic->parent_tree, &res);
+	if (unlikely (status))
+	    return status;
+
+	sp = _cairo_array_num_elements (&ic->parent_tree) - 1;
+
+	status = _cairo_array_append (&surface->page_annots, &res);
+	if (unlikely (status))
+	    return status;
+
+	_cairo_pdf_surface_update_object (surface, res);
+	_cairo_output_stream_printf (surface->output,
+				     "%d 0 obj\n"
+				     "<< /Type /Annot\n"
+				     "   /Subtype /Link\n"
+				     "   /StructParent %d\n",
+				     res.id,
+				     sp);
+
+	if (num_rects > 0) {
+	    cairo_rectangle_int_t bbox_rect;
+
+	    _cairo_output_stream_printf (surface->output,
+					 "   /QuadPoints [ ");
+	    for (i = 0; i < num_rects; i++) {
+		cairo_rectangle_t rectf;
+		cairo_rectangle_int_t recti;
+
+		_cairo_array_copy_element (&node->annot.link_attrs.rects, i, &rectf);
+		_cairo_rectangle_int_from_double (&recti, &rectf);
+		if (i == 0)
+		    bbox_rect = recti;
+		else
+		    _cairo_rectangle_union (&bbox_rect, &recti);
+
+		write_rect_to_pdf_quad_points (surface->output, &rectf, node->annot.page_height);
+		_cairo_output_stream_printf (surface->output, " ");
+	    }
+	    _cairo_output_stream_printf (surface->output,
+					 "]\n"
+					 "   /Rect [ ");
+	    write_rect_int_to_pdf_bbox (surface->output, &bbox_rect, node->annot.page_height);
+	    _cairo_output_stream_printf (surface->output, " ]\n");
+	} else {
+	    _cairo_output_stream_printf (surface->output,
+					 "   /Rect [ ");
+	    write_rect_int_to_pdf_bbox (surface->output, &node->annot.extents.extents, node->annot.page_height);
+	    _cairo_output_stream_printf (surface->output, " ]\n");
+	}
+
+	if (node->annot.link_attrs.dest) {
+	    status = _cairo_utf8_to_pdf_string (node->annot.link_attrs.dest, &dest);
+	    if (unlikely (status))
+		return status;
+	}
+
+	if (node->annot.link_attrs.link_type == TAG_LINK_DEST) {
+	    if (node->annot.link_attrs.dest) {
+		_cairo_output_stream_printf (surface->output,
+					     "   /Dest %s\n",
+					     dest);
+	    } else {
+		cairo_pdf_resource_t res;
+		int page = node->annot.link_attrs.page;
+
+		if (page < 1 || page > (int)_cairo_array_num_elements (&surface->pages))
+		    return CAIRO_INT_STATUS_TAG_ERROR;
+
+		_cairo_array_copy_element (&surface->pages, page - 1, &res);
+		_cairo_output_stream_printf (surface->output,
+					     "   /Dest [%d 0 R /XYZ %f %f 0]\n",
+					     res.id,
+					     node->annot.link_attrs.pos.x,
+					     node->annot.page_height - node->annot.link_attrs.pos.y);
+	    }
+	} else if (node->annot.link_attrs.link_type == TAG_LINK_URI) {
+	    _cairo_output_stream_printf (surface->output,
+					 "   /A <<\n"
+					 "      /Type /Action\n"
+					 "      /S /URI\n"
+					 "      /URI (%s)\n"
+					 "   >>\n",
+					 node->annot.link_attrs.uri);
+	} else if (node->annot.link_attrs.link_type == TAG_LINK_FILE) {
+	    _cairo_output_stream_printf (surface->output,
+					 "   /A <<\n"
+					 "      /Type /Action\n"
+					 "      /S /GoToR\n"
+					 "      /F (%s)\n",
+					 node->annot.link_attrs.file);
+	    if (node->annot.link_attrs.dest) {
+		_cairo_output_stream_printf (surface->output,
+					     "      /D %s\n",
+					     dest);
+	    } else {
+		_cairo_output_stream_printf (surface->output,
+					     "      /D [%d %f %f ]\n",
+					     node->annot.link_attrs.page,
+					     node->annot.link_attrs.pos.x,
+					     node->annot.link_attrs.pos.y);
+	    }
+	    _cairo_output_stream_printf (surface->output,
+					 "   >>\n");
+	}
+
+	_cairo_output_stream_printf (surface->output,
+				     "   /BS << /W 0 >>"
+				     ">>\n"
+				     "endobj\n");
+
+	status = _cairo_output_stream_get_status (surface->output);
+
+	free (dest);
+    }
+
+    return status;
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_walk_struct_tree (cairo_pdf_surface_t          *surface,
+					cairo_pdf_struct_tree_node_t *node,
+					cairo_int_status_t (*func) (cairo_pdf_surface_t *surface,
+								    cairo_pdf_struct_tree_node_t *node))
+{
+    cairo_int_status_t status;
+    cairo_pdf_struct_tree_node_t *child;
+
+    if (node->parent) {
+	status = func (surface, node);
+	if (unlikely (status))
+	    return status;
+    }
+
+    cairo_list_foreach_entry (child, cairo_pdf_struct_tree_node_t,
+			      &node->children, link)
+    {
+	status = cairo_pdf_interchange_walk_struct_tree (surface, child, func);
+	if (unlikely (status))
+	    return status;
+    }
+
+    return status;
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_struct_tree (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_pdf_struct_tree_node_t *child;
+
+    if (cairo_list_is_empty (&ic->struct_root->children))
+	return CAIRO_STATUS_SUCCESS;
+
+    surface->struct_tree_root = _cairo_pdf_surface_new_object (surface);
+    ic->struct_root->res = surface->struct_tree_root;
+
+    cairo_pdf_interchange_walk_struct_tree (surface, ic->struct_root, cairo_pdf_interchange_write_node_object);
+
+    child = cairo_list_first_entry (&ic->struct_root->children, cairo_pdf_struct_tree_node_t, link);
+    _cairo_pdf_surface_update_object (surface, surface->struct_tree_root);
+    _cairo_output_stream_printf (surface->output,
+				 "%d 0 obj\n"
+				 "<< /Type /StructTreeRoot\n"
+				 "   /ParentTree %d 0 R\n"
+				 "   /K [ %d 0 R ]\n"
+				 ">>\n"
+				 "endobj\n",
+				 surface->struct_tree_root.id,
+				 ic->parent_tree_res.id,
+				 child->res.id);
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_page_annots (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    _cairo_array_truncate (&surface->page_annots, 0);
+    ic->annot_page = _cairo_array_num_elements (&surface->pages);
+
+    cairo_pdf_interchange_walk_struct_tree (surface, ic->struct_root, cairo_pdf_interchange_write_annot);
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_page_parent_elems (cairo_pdf_surface_t *surface)
+{
+    int num_elems, i;
+    cairo_pdf_struct_tree_node_t *node;
+    cairo_pdf_resource_t res;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+
+    surface->page_parent_tree = -1;
+    num_elems = _cairo_array_num_elements (&ic->mcid_to_tree);
+    if (num_elems > 0) {
+	res = _cairo_pdf_surface_new_object (surface);
+	_cairo_output_stream_printf (surface->output,
+				     "%d 0 obj\n"
+				     "[\n",
+				     res.id);
+	for (i = 0; i < num_elems; i++) {
+	    _cairo_array_copy_element (&ic->mcid_to_tree, i, &node);
+	    _cairo_output_stream_printf (surface->output, "  %d 0 R\n", node->res.id);
+	}
+	_cairo_output_stream_printf (surface->output,
+				     "]\n"
+				     "endobj\n");
+	status = _cairo_array_append (&ic->parent_tree, &res);
+	surface->page_parent_tree = _cairo_array_num_elements (&ic->parent_tree) - 1;
+    }
+
+    return status;
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_parent_tree (cairo_pdf_surface_t *surface)
+{
+    int num_elems, i;
+    cairo_pdf_resource_t *res;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    num_elems = _cairo_array_num_elements (&ic->parent_tree);
+    if (num_elems > 0) {
+	ic->parent_tree_res = _cairo_pdf_surface_new_object (surface);
+	_cairo_output_stream_printf (surface->output,
+				     "%d 0 obj\n"
+				     "<< /Nums [\n",
+				     ic->parent_tree_res.id);
+	for (i = 0; i < num_elems; i++) {
+	    res = _cairo_array_index (&ic->parent_tree, i);
+	    if (res->id) {
+		_cairo_output_stream_printf (surface->output,
+					     "   %d %d 0 R\n",
+					     i,
+					     res->id);
+	    }
+	}
+	_cairo_output_stream_printf (surface->output,
+				     "  ]\n"
+				     ">>\n"
+				     "endobj\n");
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static void
+_collect_dest (void *entry, void *closure)
+{
+    cairo_pdf_named_dest_t *dest = entry;
+    cairo_pdf_surface_t *surface = closure;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    ic->sorted_dests[ic->num_dests++] = dest;
+}
+
+static int
+_dest_compare (const void *a, const void *b)
+{
+    const cairo_pdf_named_dest_t * const *dest_a = a;
+    const cairo_pdf_named_dest_t * const *dest_b = b;
+
+    return strcmp ((*dest_a)->attrs.name, (*dest_b)->attrs.name);
+}
+
+static cairo_int_status_t
+_cairo_pdf_interchange_write_document_dests (cairo_pdf_surface_t *surface)
+{
+    int i;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    if (ic->num_dests == 0) {
+	ic->dests_res.id = 0;
+        return CAIRO_STATUS_SUCCESS;
+    }
+
+    ic->sorted_dests = calloc (ic->num_dests, sizeof (cairo_pdf_named_dest_t *));
+    if (unlikely (ic->sorted_dests == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    ic->num_dests = 0;
+    _cairo_hash_table_foreach (ic->named_dests, _collect_dest, surface);
+    qsort (ic->sorted_dests, ic->num_dests, sizeof (cairo_pdf_named_dest_t *), _dest_compare);
+
+    ic->dests_res = _cairo_pdf_surface_new_object (surface);
+    _cairo_output_stream_printf (surface->output,
+				 "%d 0 obj\n"
+				 "<< /Names [\n",
+				 ic->dests_res.id);
+    for (i = 0; i < ic->num_dests; i++) {
+	cairo_pdf_named_dest_t *dest = ic->sorted_dests[i];
+	cairo_pdf_resource_t page_res;
+	double x = 0;
+	double y = y;
+
+	if (dest->extents.valid) {
+	    x = dest->extents.extents.x;
+	    y = dest->extents.extents.y;
+	}
+
+	if (dest->attrs.x_valid)
+	    x = dest->attrs.x;
+
+	if (dest->attrs.y_valid)
+	    y = dest->attrs.y;
+
+	_cairo_array_copy_element (&surface->pages, dest->page - 1, &page_res);
+	_cairo_output_stream_printf (surface->output,
+				     "   (%s) [ %d 0 R /XYZ %f %f ]\n",
+				     dest->attrs.name,
+				     page_res.id,
+				     x,
+				     surface->height - y);
+    }
+    _cairo_output_stream_printf (surface->output,
+				     "  ]\n"
+				     ">>\n"
+				     "endobj\n");
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_int_status_t
+cairo_pdf_interchange_write_names_dict (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status;
+
+    status = _cairo_pdf_interchange_write_document_dests (surface);
+    if (unlikely (status))
+	return status;
+
+    surface->names_dict_res.id = 0;
+    if (ic->dests_res.id != 0) {
+	surface->names_dict_res = _cairo_pdf_surface_new_object (surface);
+	_cairo_output_stream_printf (surface->output,
+				     "%d 0 obj\n"
+				     "<< /Dests %d 0 R >>\n"
+				     "endobj\n",
+				     surface->names_dict_res.id,
+				     ic->dests_res.id);
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static void
+init_named_dest_key (cairo_pdf_named_dest_t *dest)
+{
+    dest->base.hash = _cairo_hash_bytes (_CAIRO_HASH_INIT_VALUE,
+					 dest->attrs.name,
+					 strlen (dest->attrs.name));
+}
+
+static cairo_bool_t
+_named_dest_equal (const void *key_a, const void *key_b)
+{
+    const cairo_pdf_named_dest_t *a = key_a;
+    const cairo_pdf_named_dest_t *b = key_b;
+
+    return strcmp (a->attrs.name, b->attrs.name) == 0;
+}
+
+static void
+_named_dest_pluck (void *entry, void *closure)
+{
+    cairo_pdf_named_dest_t *dest = entry;
+    cairo_hash_table_t *table = closure;
+
+    _cairo_hash_table_remove (table, &dest->base);
+    free (dest->attrs.name);
+    free (dest);
+}
+
+static cairo_int_status_t
+_cairo_pdf_interchange_begin_structure_tag (cairo_pdf_surface_t    *surface,
+					    cairo_tag_type_t        tag_type,
+					    const char             *name,
+					    const char             *attributes)
+{
+    int page_num, mcid;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	status = add_tree_node (surface, ic->current_node, name, &ic->current_node);
+	if (unlikely (status))
+	    return status;
+
+	_cairo_tag_stack_set_top_data (&ic->analysis_tag_stack, ic->current_node);
+
+	if (tag_type & TAG_TYPE_LINK) {
+	    status = _cairo_tag_parse_link_attributes (attributes, &ic->current_node->annot.link_attrs);
+	    if (unlikely (status))
+		return status;
+
+	    ic->current_node->annot.page_height = surface->height;
+	    cairo_list_add_tail (&ic->current_node->annot.extents.link, &ic->extents_list);
+	}
+
+    } else if (surface->paginated_mode == CAIRO_PAGINATED_MODE_RENDER) {
+	ic->current_node = _cairo_tag_stack_top_elem (&ic->render_tag_stack)->data;
+	assert (ic->current_node != NULL);
+	if (is_leaf_node (ic->current_node)) {
+	    page_num = _cairo_array_num_elements (&surface->pages);
+	    add_mcid_to_node (surface, ic->current_node, page_num, &mcid);
+	    status = _cairo_pdf_operators_tag_begin (&surface->pdf_operators, name, mcid);
+	}
+    }
+
+    return status;
+}
+
+static cairo_int_status_t
+_cairo_pdf_interchange_begin_dest_tag (cairo_pdf_surface_t    *surface,
+				       cairo_tag_type_t        tag_type,
+				       const char             *name,
+				       const char             *attributes)
+{
+    cairo_pdf_named_dest_t *dest;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	dest = calloc (1, sizeof (cairo_pdf_named_dest_t));
+	if (unlikely (dest == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+	status = _cairo_tag_parse_dest_attributes (attributes, &dest->attrs);
+	if (unlikely (status))
+	    return status;
+
+	dest->page_height = surface->height;
+	dest->page = _cairo_array_num_elements (&surface->pages);
+	init_named_dest_key (dest);
+	status = _cairo_hash_table_insert (ic->named_dests, &dest->base);
+	if (unlikely (status))
+	    return status;
+
+	_cairo_tag_stack_set_top_data (&ic->analysis_tag_stack, dest);
+	cairo_list_add_tail (&dest->extents.link, &ic->extents_list);
+	ic->num_dests++;
+    }
+
+    return status;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_tag_begin (cairo_pdf_surface_t    *surface,
+				  const char             *name,
+				  const char             *attributes)
+{
+    cairo_int_status_t status;
+    cairo_tag_type_t tag_type;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    void *ptr;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	status = _cairo_tag_stack_push (&ic->analysis_tag_stack, name, attributes);
+
+    } else if (surface->paginated_mode == CAIRO_PAGINATED_MODE_RENDER) {
+	status = _cairo_tag_stack_push (&ic->render_tag_stack, name, attributes);
+	_cairo_array_copy_element (&ic->push_data, ic->push_data_index++, &ptr);
+	_cairo_tag_stack_set_top_data (&ic->render_tag_stack, ptr);
+    }
+
+    if (unlikely (status))
+	return status;
+
+    tag_type = _cairo_tag_get_type (name);
+    if (tag_type & TAG_TYPE_STRUCTURE) {
+	status = _cairo_pdf_interchange_begin_structure_tag (surface, tag_type, name, attributes);
+	if (unlikely (status))
+	    return status;
+    }
+
+    if (tag_type & TAG_TYPE_DEST) {
+	status = _cairo_pdf_interchange_begin_dest_tag (surface, tag_type, name, attributes);
+	if (unlikely (status))
+	    return status;
+    }
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	ptr = _cairo_tag_stack_top_elem (&ic->analysis_tag_stack)->data;
+	status = _cairo_array_append (&ic->push_data, &ptr);
+    }
+
+    return status;
+}
+
+static cairo_int_status_t
+_cairo_pdf_interchange_end_structure_tag (cairo_pdf_surface_t    *surface,
+					  cairo_tag_type_t        tag_type,
+					  cairo_tag_stack_elem_t *elem)
+{
+    const cairo_pdf_struct_tree_node_t *node;
+    struct tag_extents *tag, *next;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+
+    assert (elem->data != NULL);
+    node = elem->data;
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	if (tag_type & TAG_TYPE_LINK) {
+	    cairo_list_foreach_entry_safe (tag, next, struct tag_extents,
+					   &ic->extents_list, link) {
+		if (tag == &node->annot.extents) {
+		    cairo_list_del (&tag->link);
+		    break;
+		}
+	    }
+	}
+    } else if (surface->paginated_mode == CAIRO_PAGINATED_MODE_RENDER) {
+	if (is_leaf_node (ic->current_node)) {
+	    status = _cairo_pdf_operators_tag_end (&surface->pdf_operators);
+	    if (unlikely (status))
+		return status;
+	}
+    }
+
+    ic->current_node = ic->current_node->parent;
+    assert (ic->current_node != NULL);
+
+    return status;
+}
+
+static cairo_int_status_t
+_cairo_pdf_interchange_end_dest_tag (cairo_pdf_surface_t    *surface,
+				     cairo_tag_type_t        tag_type,
+				     cairo_tag_stack_elem_t *elem)
+{
+    struct tag_extents *tag, *next;
+    cairo_pdf_named_dest_t *dest;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	assert (elem->data != NULL);
+	dest = (cairo_pdf_named_dest_t *) elem->data;
+	cairo_list_foreach_entry_safe (tag, next, struct tag_extents,
+					   &ic->extents_list, link) {
+	    if (tag == &dest->extents) {
+		cairo_list_del (&tag->link);
+		break;
+	    }
+	}
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_tag_end (cairo_pdf_surface_t *surface,
+				const char          *name)
+{
+    cairo_int_status_t status;
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_tag_type_t tag_type;
+    cairo_tag_stack_elem_t *elem;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE)
+	status = _cairo_tag_stack_pop (&ic->analysis_tag_stack, name, &elem);
+    else if (surface->paginated_mode == CAIRO_PAGINATED_MODE_RENDER)
+	status = _cairo_tag_stack_pop (&ic->render_tag_stack, name, &elem);
+
+    if (unlikely (status))
+	return status;
+
+    tag_type = _cairo_tag_get_type (name);
+    if (tag_type & TAG_TYPE_STRUCTURE) {
+	status = _cairo_pdf_interchange_end_structure_tag (surface, tag_type, elem);
+	if (unlikely (status))
+	    goto cleanup;
+    }
+
+    if (tag_type & TAG_TYPE_DEST) {
+	status = _cairo_pdf_interchange_end_dest_tag (surface, tag_type, elem);
+	if (unlikely (status))
+	    goto cleanup;
+    }
+
+  cleanup:
+    _cairo_tag_stack_free_elem (elem);
+
+    return status;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_add_operation_extents (cairo_pdf_surface_t         *surface,
+					      const cairo_rectangle_int_t *extents)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    struct tag_extents *tag;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	cairo_list_foreach_entry (tag, struct tag_extents, &ic->extents_list, link) {
+	    if (tag->valid) {
+		_cairo_rectangle_union (&tag->extents, extents);
+	    } else {
+		tag->extents = *extents;
+		tag->valid = TRUE;
+	    }
+	}
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_begin_page_content (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+    int page_num, mcid;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
+	_cairo_array_truncate (&ic->mcid_to_tree, 0);
+	_cairo_array_truncate (&ic->push_data, 0);
+	ic->begin_page_node = ic->current_node;
+    } else if (surface->paginated_mode == CAIRO_PAGINATED_MODE_RENDER) {
+	ic->push_data_index = 0;
+	ic->current_node = ic->begin_page_node;
+	if (ic->end_page_node && is_leaf_node (ic->end_page_node)) {
+	    page_num = _cairo_array_num_elements (&surface->pages);
+	    add_mcid_to_node (surface, ic->end_page_node, page_num, &mcid);
+	    status = _cairo_pdf_operators_tag_begin (&surface->pdf_operators,
+						     ic->end_page_node->name,
+						     mcid);
+	}
+    }
+
+    return status;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_end_page_content (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+
+    if (surface->paginated_mode == CAIRO_PAGINATED_MODE_RENDER) {
+	ic->end_page_node = ic->current_node;
+	if (is_leaf_node (ic->current_node))
+	    status = _cairo_pdf_operators_tag_end (&surface->pdf_operators);
+    }
+
+    return status;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_write_page_objects (cairo_pdf_surface_t *surface)
+{
+    cairo_int_status_t status;
+
+    status = cairo_pdf_interchange_write_page_annots (surface);
+     if (unlikely (status))
+	return status;
+
+    return cairo_pdf_interchange_write_page_parent_elems (surface);
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_write_document_objects (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+    cairo_int_status_t status = CAIRO_STATUS_SUCCESS;
+
+    status = cairo_pdf_interchange_write_parent_tree (surface);
+    if (unlikely (status))
+	return status;
+
+    status = cairo_pdf_interchange_write_struct_tree (surface);
+    if (unlikely (status))
+	return status;
+
+    if (_cairo_tag_stack_get_structure_type (&ic->analysis_tag_stack) == TAG_TREE_TYPE_TAGGED)
+	surface->tagged = TRUE;
+
+    status = cairo_pdf_interchange_write_names_dict (surface);
+
+    return status;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_init (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    _cairo_tag_stack_init (&ic->analysis_tag_stack);
+    _cairo_tag_stack_init (&ic->render_tag_stack);
+    _cairo_array_init (&ic->push_data, sizeof(void *));
+    ic->struct_root = calloc (1, sizeof(cairo_pdf_struct_tree_node_t));
+    if (unlikely (ic->struct_root == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    cairo_list_init (&ic->struct_root->children);
+    _cairo_array_init (&ic->struct_root->mcid, sizeof(struct page_mcid));
+    ic->current_node = ic->struct_root;
+    ic->begin_page_node = NULL;
+    ic->end_page_node = NULL;
+    _cairo_array_init (&ic->parent_tree, sizeof(cairo_pdf_resource_t));
+    _cairo_array_init (&ic->mcid_to_tree, sizeof(cairo_pdf_struct_tree_node_t *));
+    ic->parent_tree_res.id = 0;
+    cairo_list_init (&ic->extents_list);
+    ic->named_dests = _cairo_hash_table_create (_named_dest_equal);
+    if (unlikely (ic->named_dests == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    ic->num_dests = 0;
+    ic->sorted_dests = NULL;
+    ic->dests_res.id = 0;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_int_status_t
+_cairo_pdf_interchange_fini (cairo_pdf_surface_t *surface)
+{
+    cairo_pdf_interchange_t *ic = &surface->interchange;
+
+    _cairo_tag_stack_fini (&ic->analysis_tag_stack);
+    _cairo_tag_stack_fini (&ic->render_tag_stack);
+    _cairo_array_fini (&ic->push_data);
+    free_node (ic->struct_root);
+    _cairo_array_fini (&ic->mcid_to_tree);
+    _cairo_array_fini (&ic->parent_tree);
+    _cairo_hash_table_foreach (ic->named_dests, _named_dest_pluck, ic->named_dests);
+    _cairo_hash_table_destroy (ic->named_dests);
+    free (ic->sorted_dests);
+
+    return CAIRO_STATUS_SUCCESS;
+}
diff --git a/src/cairo-pdf-operators-private.h b/src/cairo-pdf-operators-private.h
index 4314a042e..ed8be7f96 100644
--- a/src/cairo-pdf-operators-private.h
+++ b/src/cairo-pdf-operators-private.h
@@ -173,4 +173,12 @@ _cairo_pdf_operators_show_text_glyphs (cairo_pdf_operators_t	  *pdf_operators,
 				       cairo_text_cluster_flags_t  cluster_flags,
 				       cairo_scaled_font_t	  *scaled_font);
 
+cairo_private cairo_int_status_t
+_cairo_pdf_operators_tag_begin (cairo_pdf_operators_t *pdf_operators,
+				const char            *tag_name,
+				int                    mcid);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_operators_tag_end (cairo_pdf_operators_t *pdf_operators);
+
 #endif /* CAIRO_PDF_OPERATORS_H */
diff --git a/src/cairo-pdf-operators.c b/src/cairo-pdf-operators.c
index dec8ca07f..99a8dc800 100644
--- a/src/cairo-pdf-operators.c
+++ b/src/cairo-pdf-operators.c
@@ -1554,4 +1554,41 @@ _cairo_pdf_operators_show_text_glyphs (cairo_pdf_operators_t	  *pdf_operators,
     return _cairo_output_stream_get_status (pdf_operators->stream);
 }
 
+cairo_int_status_t
+_cairo_pdf_operators_tag_begin (cairo_pdf_operators_t *pdf_operators,
+				const char            *tag_name,
+				int                    mcid)
+{
+    cairo_status_t status;
+
+    if (pdf_operators->in_text_object) {
+	status = _cairo_pdf_operators_end_text (pdf_operators);
+	if (unlikely (status))
+	    return status;
+    }
+
+    _cairo_output_stream_printf (pdf_operators->stream,
+				 "/%s << /MCID %d >> BDC\n",
+				 tag_name,
+				 mcid);
+
+    return _cairo_output_stream_get_status (pdf_operators->stream);
+}
+
+cairo_int_status_t
+_cairo_pdf_operators_tag_end (cairo_pdf_operators_t *pdf_operators)
+{
+    cairo_status_t status;
+
+    if (pdf_operators->in_text_object) {
+	status = _cairo_pdf_operators_end_text (pdf_operators);
+	if (unlikely (status))
+	    return status;
+    }
+
+    _cairo_output_stream_printf (pdf_operators->stream, "EMC\n");
+
+    return _cairo_output_stream_get_status (pdf_operators->stream);
+}
+
 #endif /* CAIRO_HAS_PDF_OPERATORS */
diff --git a/src/cairo-pdf-surface-private.h b/src/cairo-pdf-surface-private.h
index 0229dbc45..cbe4599a1 100644
--- a/src/cairo-pdf-surface-private.h
+++ b/src/cairo-pdf-surface-private.h
@@ -48,6 +48,8 @@
 #include "cairo-surface-clipper-private.h"
 #include "cairo-pdf-operators-private.h"
 #include "cairo-path-fixed-private.h"
+#include "cairo-tag-attributes-private.h"
+#include "cairo-tag-stack-private.h"
 
 typedef struct _cairo_pdf_resource {
     unsigned int id;
@@ -154,6 +156,66 @@ typedef struct _cairo_pdf_jbig2_global {
     cairo_bool_t emitted;
 } cairo_pdf_jbig2_global_t;
 
+/* cairo-pdf-interchange.c types */
+
+struct page_mcid {
+    int page;
+    int mcid;
+};
+
+struct tag_extents {
+    cairo_rectangle_int_t extents;
+    cairo_bool_t valid;
+    cairo_list_t link;
+};
+
+typedef struct _cairo_pdf_struct_tree_node {
+    char *name;
+    cairo_pdf_resource_t res;
+    struct _cairo_pdf_struct_tree_node *parent;
+    cairo_list_t children;
+    cairo_array_t mcid; /* array of struct page_mcid */
+    struct {
+	struct tag_extents extents;
+	cairo_pdf_resource_t res;
+	cairo_link_attrs_t link_attrs;
+	double page_height;
+    } annot;
+    cairo_list_t link;
+} cairo_pdf_struct_tree_node_t;
+
+typedef struct _cairo_pdf_named_dest {
+    cairo_hash_entry_t base;
+    struct tag_extents extents;
+    cairo_dest_attrs_t attrs;
+    int page;
+    double page_height;
+    cairo_bool_t referenced;
+} cairo_pdf_named_dest_t;
+
+typedef struct _cairo_pdf_interchange {
+    cairo_tag_stack_t analysis_tag_stack;
+    cairo_tag_stack_t render_tag_stack;
+    cairo_array_t push_data; /* records analysis_tag_stack data field for each push */
+    int push_data_index;
+    cairo_pdf_struct_tree_node_t *struct_root;
+    cairo_pdf_struct_tree_node_t *current_node;
+    cairo_pdf_struct_tree_node_t *begin_page_node;
+    cairo_pdf_struct_tree_node_t *end_page_node;
+    cairo_array_t parent_tree; /* parent tree resources */
+    cairo_array_t mcid_to_tree; /* mcid to tree node mapping for current page */
+    cairo_pdf_resource_t parent_tree_res;
+    cairo_list_t extents_list;
+    cairo_hash_table_t *named_dests;
+    int num_dests;
+    cairo_pdf_named_dest_t **sorted_dests;
+    cairo_pdf_resource_t dests_res;
+    int annot_page;
+
+} cairo_pdf_interchange_t;
+
+/* pdf surface data */
+
 typedef struct _cairo_pdf_surface cairo_pdf_surface_t;
 
 struct _cairo_pdf_surface {
@@ -186,6 +248,7 @@ struct _cairo_pdf_surface {
 
     cairo_pdf_resource_t next_available_resource;
     cairo_pdf_resource_t pages_resource;
+    cairo_pdf_resource_t struct_tree_root;
 
     cairo_pdf_version_t pdf_version;
     cairo_bool_t compress_content;
@@ -231,7 +294,55 @@ struct _cairo_pdf_surface {
     double current_color_blue;
     double current_color_alpha;
 
+    cairo_pdf_interchange_t interchange;
+    int page_parent_tree; /* -1 if not used */
+    cairo_array_t page_annots;
+    cairo_bool_t tagged;
+    cairo_pdf_resource_t names_dict_res;
+
     cairo_surface_t *paginated_surface;
 };
 
+cairo_private cairo_pdf_resource_t
+_cairo_pdf_surface_new_object (cairo_pdf_surface_t *surface);
+
+cairo_private void
+_cairo_pdf_surface_update_object (cairo_pdf_surface_t	*surface,
+				  cairo_pdf_resource_t	 resource);
+
+cairo_int_status_t
+_cairo_utf8_to_pdf_string (const char *utf8, char **str_out);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_init (cairo_pdf_surface_t *surface);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_fini (cairo_pdf_surface_t *surface);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_begin_page_content (cairo_pdf_surface_t *surface);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_end_page_content (cairo_pdf_surface_t *surface);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_tag_begin (cairo_pdf_surface_t    *surface,
+				  const char             *name,
+				  const char             *attributes);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_tag_end (cairo_pdf_surface_t *surface,
+				const char          *name);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_add_operation_extents (cairo_pdf_surface_t         *surface,
+					      const cairo_rectangle_int_t *extents);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_write_page_objects (cairo_pdf_surface_t *surface);
+
+cairo_private cairo_int_status_t
+_cairo_pdf_interchange_write_document_objects (cairo_pdf_surface_t *surface);
+
+
 #endif /* CAIRO_PDF_SURFACE_PRIVATE_H */
diff --git a/src/cairo-pdf-surface.c b/src/cairo-pdf-surface.c
index 3f879fb2e..a32dfb6bc 100644
--- a/src/cairo-pdf-surface.c
+++ b/src/cairo-pdf-surface.c
@@ -209,9 +209,6 @@ typedef struct _cairo_pdf_alpha_linear_function {
     double               alpha2;
 } cairo_pdf_alpha_linear_function_t;
 
-static cairo_pdf_resource_t
-_cairo_pdf_surface_new_object (cairo_pdf_surface_t *surface);
-
 static void
 _cairo_pdf_surface_clear (cairo_pdf_surface_t *surface);
 
@@ -262,7 +259,7 @@ _cairo_pdf_source_surface_equal (const void *key_a, const void *key_b);
 static const cairo_surface_backend_t cairo_pdf_surface_backend;
 static const cairo_paginated_surface_backend_t cairo_pdf_surface_paginated_backend;
 
-static cairo_pdf_resource_t
+cairo_pdf_resource_t
 _cairo_pdf_surface_new_object (cairo_pdf_surface_t *surface)
 {
     cairo_pdf_resource_t resource;
@@ -283,7 +280,7 @@ _cairo_pdf_surface_new_object (cairo_pdf_surface_t *surface)
     return resource;
 }
 
-static void
+void
 _cairo_pdf_surface_update_object (cairo_pdf_surface_t	*surface,
 				  cairo_pdf_resource_t	 resource)
 {
@@ -416,6 +413,7 @@ _cairo_pdf_surface_create_for_stream_internal (cairo_output_stream_t	*output,
         goto BAIL2;
     }
 
+    surface->struct_tree_root.id = 0;
     surface->pdf_version = CAIRO_PDF_VERSION_1_5;
     surface->compress_content = TRUE;
     surface->pdf_stream.active = FALSE;
@@ -445,6 +443,15 @@ _cairo_pdf_surface_create_for_stream_internal (cairo_output_stream_t	*output,
 						    surface);
     _cairo_pdf_operators_enable_actual_text(&surface->pdf_operators, TRUE);
 
+    status = _cairo_pdf_interchange_init (surface);
+    if (unlikely (status))
+	goto BAIL2;
+
+    surface->page_parent_tree = -1;
+    _cairo_array_init (&surface->page_annots, sizeof (cairo_pdf_resource_t));
+    surface->tagged = FALSE;
+    surface->names_dict_res.id = 0;
+
     surface->paginated_surface =  _cairo_paginated_surface_create (
 	                                  &surface->base,
 					  CAIRO_CONTENT_COLOR_ALPHA,
@@ -742,6 +749,7 @@ _cairo_pdf_surface_clear (cairo_pdf_surface_t *surface)
     }
     _cairo_array_truncate (&surface->smask_groups, 0);
     _cairo_array_truncate (&surface->knockout_group, 0);
+    _cairo_array_truncate (&surface->page_annots, 0);
 }
 
 static void
@@ -2071,6 +2079,10 @@ _cairo_pdf_surface_finish (void *abstract_surface)
 
     _cairo_pdf_surface_write_pages (surface);
 
+    status = _cairo_pdf_interchange_write_document_objects (surface);
+    if (unlikely (status))
+	return status;
+
     info = _cairo_pdf_surface_write_info (surface);
     if (info.id == 0 && status == CAIRO_STATUS_SUCCESS)
 	status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
@@ -2145,6 +2157,7 @@ _cairo_pdf_surface_finish (void *abstract_surface)
     _cairo_array_fini (&surface->smask_groups);
     _cairo_array_fini (&surface->fonts);
     _cairo_array_fini (&surface->knockout_group);
+    _cairo_array_fini (&surface->page_annots);
 
     if (surface->font_subsets) {
 	_cairo_scaled_font_subsets_destroy (surface->font_subsets);
@@ -2164,13 +2177,15 @@ _cairo_pdf_surface_finish (void *abstract_surface)
 
     _cairo_surface_clipper_reset (&surface->clipper);
 
-    return status;
+    return _cairo_pdf_interchange_fini (surface);
 }
 
 static cairo_int_status_t
 _cairo_pdf_surface_start_page (void *abstract_surface)
 {
     cairo_pdf_surface_t *surface = abstract_surface;
+    cairo_pdf_resource_t page;
+    cairo_int_status_t status;
 
     /* Document header */
     if (! surface->header_emitted) {
@@ -2196,6 +2211,14 @@ _cairo_pdf_surface_start_page (void *abstract_surface)
     _cairo_pdf_group_resources_clear (&surface->resources);
     surface->in_xobject = FALSE;
 
+    page = _cairo_pdf_surface_new_object (surface);
+    if (page.id == 0)
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    status = _cairo_array_append (&surface->pages, &page);
+    if (unlikely (status))
+	return status;
+
     return CAIRO_STATUS_SUCCESS;
 }
 
@@ -4678,6 +4701,10 @@ _cairo_pdf_surface_show_page (void *abstract_surface)
     cairo_pdf_surface_t *surface = abstract_surface;
     cairo_int_status_t status;
 
+    status = _cairo_pdf_interchange_end_page_content (surface);
+    if (unlikely (status))
+	return status;
+
     status = _cairo_pdf_surface_close_content_stream (surface);
     if (unlikely (status))
 	return status;
@@ -4769,8 +4796,8 @@ _cairo_pdf_surface_write_pages (cairo_pdf_surface_t *surface)
 				 "endobj\n");
 }
 
-static cairo_int_status_t
-_utf8_to_pdf_string (const char *utf8, char **str_out)
+cairo_int_status_t
+_cairo_utf8_to_pdf_string (const char *utf8, char **str_out)
 {
     int i;
     int len;
@@ -5115,7 +5142,7 @@ _cairo_pdf_surface_emit_cff_font (cairo_pdf_surface_t		*surface,
     if (subset->family_name_utf8) {
 	char *pdf_str;
 
-	status = _utf8_to_pdf_string (subset->family_name_utf8, &pdf_str);
+	status = _cairo_utf8_to_pdf_string (subset->family_name_utf8, &pdf_str);
 	if (likely (status == CAIRO_INT_STATUS_SUCCESS)) {
 	    _cairo_output_stream_printf (surface->output,
 					 "   /FontFamily %s\n",
@@ -5561,7 +5588,7 @@ _cairo_pdf_surface_emit_truetype_font_subset (cairo_pdf_surface_t		*surface,
     if (subset.family_name_utf8) {
 	char *pdf_str;
 
-	status = _utf8_to_pdf_string (subset.family_name_utf8, &pdf_str);
+	status = _cairo_utf8_to_pdf_string (subset.family_name_utf8, &pdf_str);
 	if (likely (status == CAIRO_INT_STATUS_SUCCESS)) {
 	    _cairo_output_stream_printf (surface->output,
 					 "   /FontFamily %s\n",
@@ -6066,12 +6093,30 @@ _cairo_pdf_surface_write_catalog (cairo_pdf_surface_t *surface)
     _cairo_output_stream_printf (surface->output,
 				 "%d 0 obj\n"
 				 "<< /Type /Catalog\n"
-				 "   /Pages %d 0 R\n"
-				 ">>\n"
-				 "endobj\n",
+				 "   /Pages %d 0 R\n",
 				 catalog.id,
 				 surface->pages_resource.id);
 
+    if (surface->struct_tree_root.id != 0) {
+	_cairo_output_stream_printf (surface->output,
+				     "   /StructTreeRoot %d 0 R\n",
+				     surface->struct_tree_root.id);
+	if (surface->tagged) {
+	    _cairo_output_stream_printf (surface->output,
+					 "   /MarkInfo << /Marked true >>\n");
+	}
+    }
+
+    if (surface->names_dict_res.id != 0) {
+	_cairo_output_stream_printf (surface->output,
+				     "   /Names %d 0 R\n",
+				     surface->names_dict_res.id);
+    }
+
+    _cairo_output_stream_printf (surface->output,
+				 ">>\n"
+				 "endobj\n");
+
     return catalog;
 }
 
@@ -6436,9 +6481,14 @@ _cairo_pdf_surface_write_patterns_and_smask_groups (cairo_pdf_surface_t *surface
 static cairo_int_status_t
 _cairo_pdf_surface_write_page (cairo_pdf_surface_t *surface)
 {
-    cairo_pdf_resource_t page, knockout, res;
+    cairo_pdf_resource_t knockout, res;
+    cairo_pdf_resource_t *page;
     cairo_int_status_t status;
-    unsigned int i, len;
+    unsigned int i, len, page_num, num_annots;
+
+    status = _cairo_pdf_interchange_write_page_objects (surface);
+    if (unlikely (status))
+	return status;
 
     _cairo_pdf_group_resources_clear (&surface->resources);
     if (surface->has_fallback_images) {
@@ -6492,10 +6542,9 @@ _cairo_pdf_surface_write_page (cairo_pdf_surface_t *surface)
 	    return status;
     }
 
-    page = _cairo_pdf_surface_new_object (surface);
-    if (page.id == 0)
-	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
-
+    page_num = _cairo_array_num_elements (&surface->pages);
+    page = _cairo_array_index (&surface->pages, page_num - 1);
+    _cairo_pdf_surface_update_object (surface, *page);
     _cairo_output_stream_printf (surface->output,
 				 "%d 0 obj\n"
 				 "<< /Type /Page\n"
@@ -6508,19 +6557,36 @@ _cairo_pdf_surface_write_page (cairo_pdf_surface_t *surface)
 				 "      /I true\n"
 				 "      /CS /DeviceRGB\n"
 				 "   >>\n"
-				 "   /Resources %d 0 R\n"
-				 ">>\n"
-				 "endobj\n",
-				 page.id,
+				 "   /Resources %d 0 R\n",
+				 page->id,
 				 surface->pages_resource.id,
 				 surface->width,
 				 surface->height,
 				 surface->content.id,
 				 surface->content_resources.id);
 
-    status = _cairo_array_append (&surface->pages, &page);
-    if (unlikely (status))
-	return status;
+    if (surface->page_parent_tree >= 0) {
+	_cairo_output_stream_printf (surface->output,
+				     "   /StructParents %d\n",
+				     surface->page_parent_tree);
+    }
+
+    num_annots = _cairo_array_num_elements (&surface->page_annots);
+    if (num_annots > 0) {
+	_cairo_output_stream_printf (surface->output,
+				     "   /Annots [ ");
+	for (i = 0; i < num_annots; i++) {
+	    _cairo_array_copy_element (&surface->page_annots, i, &res);
+	    _cairo_output_stream_printf (surface->output,
+					 "%d 0 R ",
+					 res.id);
+	}
+	_cairo_output_stream_printf (surface->output, "]\n");
+    }
+
+    _cairo_output_stream_printf (surface->output,
+				 ">>\n"
+				 "endobj\n");
 
     status = _cairo_pdf_surface_write_patterns_and_smask_groups (surface);
     if (unlikely (status))
@@ -6764,7 +6830,11 @@ _cairo_pdf_surface_start_fallback (cairo_pdf_surface_t *surface)
     bbox.p1.y = 0;
     bbox.p2.x = surface->width;
     bbox.p2.y = surface->height;
-    return _cairo_pdf_surface_open_content_stream (surface, &bbox, NULL, TRUE, TRUE);
+    status = _cairo_pdf_surface_open_content_stream (surface, &bbox, NULL, TRUE, TRUE);
+    if (unlikely (status))
+	return status;
+
+    return _cairo_pdf_interchange_begin_page_content (surface);
 }
 
 /* If source is an opaque image and mask is an image and both images
@@ -7040,6 +7110,10 @@ _cairo_pdf_surface_paint (void			*abstract_surface,
     if (unlikely (status))
 	return status;
 
+    status = _cairo_pdf_interchange_add_operation_extents (surface, &extents.bounded);
+    if (unlikely (status))
+	return status;
+
     if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
 	status = _cairo_pdf_surface_analyze_operation (surface, op, source, &extents.bounded);
 	goto cleanup;
@@ -7164,6 +7238,10 @@ _cairo_pdf_surface_mask (void			*abstract_surface,
     if (unlikely (status))
 	return status;
 
+    status = _cairo_pdf_interchange_add_operation_extents (surface, &extents.bounded);
+    if (unlikely (status))
+	return status;
+
     if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
 	cairo_int_status_t source_status, mask_status;
 
@@ -7333,6 +7411,10 @@ _cairo_pdf_surface_stroke (void			*abstract_surface,
 	    goto cleanup;
     }
 
+    status = _cairo_pdf_interchange_add_operation_extents (surface, &extents.bounded);
+    if (unlikely (status))
+	goto cleanup;
+
     if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
 	status = _cairo_pdf_surface_analyze_operation (surface, op, source, &extents.bounded);
 	goto cleanup;
@@ -7467,6 +7549,10 @@ _cairo_pdf_surface_fill (void			*abstract_surface,
 	    goto cleanup;
     }
 
+    status = _cairo_pdf_interchange_add_operation_extents (surface, &extents.bounded);
+    if (unlikely (status))
+	goto cleanup;
+
     if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
 	status = _cairo_pdf_surface_analyze_operation (surface, op, source, &extents.bounded);
 	goto cleanup;
@@ -7685,6 +7771,10 @@ _cairo_pdf_surface_fill_stroke (void			*abstract_surface,
 	    goto cleanup;
     }
 
+    status = _cairo_pdf_interchange_add_operation_extents (surface, &extents.bounded);
+    if (unlikely (status))
+	goto cleanup;
+
     fill_pattern_res.id = 0;
     gstate_res.id = 0;
     status = _cairo_pdf_surface_add_pdf_pattern (surface, fill_source,
@@ -7780,6 +7870,10 @@ _cairo_pdf_surface_show_text_glyphs (void			*abstract_surface,
     if (unlikely (status))
 	return status;
 
+    status = _cairo_pdf_interchange_add_operation_extents (surface, &extents.bounded);
+    if (unlikely (status))
+	return status;
+
     if (surface->paginated_mode == CAIRO_PAGINATED_MODE_ANALYZE) {
 	status = _cairo_pdf_surface_analyze_operation (surface, op, source, &extents.bounded);
 	goto cleanup;
@@ -7918,12 +8012,39 @@ _cairo_pdf_surface_get_supported_mime_types (void		 *abstract_surface)
 }
 
 static cairo_int_status_t
+_cairo_pdf_surface_tag (void			   *abstract_surface,
+			cairo_bool_t                begin,
+			const char                 *tag_name,
+			const char                 *attributes,
+			const cairo_pattern_t	   *source,
+			const cairo_stroke_style_t *style,
+			const cairo_matrix_t	   *ctm,
+			const cairo_matrix_t	   *ctm_inverse,
+			const cairo_clip_t	   *clip)
+{
+    cairo_pdf_surface_t *surface = abstract_surface;
+    cairo_int_status_t status = 0;
+
+    if (begin)
+	status = _cairo_pdf_interchange_tag_begin (surface, tag_name, attributes);
+    else
+	status = _cairo_pdf_interchange_tag_end (surface, tag_name);
+
+    return status;
+}
+
+static cairo_int_status_t
 _cairo_pdf_surface_set_paginated_mode (void			*abstract_surface,
 				       cairo_paginated_mode_t	 paginated_mode)
 {
     cairo_pdf_surface_t *surface = abstract_surface;
+    cairo_int_status_t status;
 
     surface->paginated_mode = paginated_mode;
+    status = _cairo_pdf_interchange_begin_page_content (surface);
+    if (unlikely (status))
+	return status;
+
     if (paginated_mode == CAIRO_PAGINATED_MODE_RENDER) {
 	surface->surface_extents.x = 0;
 	surface->surface_extents.y = 0;
@@ -7969,6 +8090,7 @@ static const cairo_surface_backend_t cairo_pdf_surface_backend = {
     _cairo_pdf_surface_has_show_text_glyphs,
     _cairo_pdf_surface_show_text_glyphs,
     _cairo_pdf_surface_get_supported_mime_types,
+    _cairo_pdf_surface_tag,
 };
 
 static const cairo_paginated_surface_backend_t
diff --git a/src/cairo-region.c b/src/cairo-region.c
index b738c4437..c1d35e174 100644
--- a/src/cairo-region.c
+++ b/src/cairo-region.c
@@ -110,6 +110,7 @@ _cairo_region_create_in_error (cairo_status_t status)
     case CAIRO_STATUS_PNG_ERROR:
     case CAIRO_STATUS_FREETYPE_ERROR:
     case CAIRO_STATUS_WIN32_GDI_ERROR:
+    case CAIRO_STATUS_TAG_ERROR:
     default:
 	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 	return (cairo_region_t *) &_cairo_region_nil;
diff --git a/src/cairo-spans.c b/src/cairo-spans.c
index d20cd5ad4..59452c0ba 100644
--- a/src/cairo-spans.c
+++ b/src/cairo-spans.c
@@ -131,6 +131,7 @@ _cairo_scan_converter_create_in_error (cairo_status_t status)
     case CAIRO_STATUS_PNG_ERROR:
     case CAIRO_STATUS_FREETYPE_ERROR:
     case CAIRO_STATUS_WIN32_GDI_ERROR:
+    case CAIRO_STATUS_TAG_ERROR:
     default:
 	break;
     }
@@ -247,6 +248,7 @@ _cairo_span_renderer_create_in_error (cairo_status_t status)
     case CAIRO_STATUS_PNG_ERROR: RETURN_NIL;
     case CAIRO_STATUS_FREETYPE_ERROR: RETURN_NIL;
     case CAIRO_STATUS_WIN32_GDI_ERROR: RETURN_NIL;
+    case CAIRO_STATUS_TAG_ERROR: RETURN_NIL;
     default:
 	break;
     }
diff --git a/src/cairo-surface.c b/src/cairo-surface.c
index 8a83d55d6..8f05db8c7 100644
--- a/src/cairo-surface.c
+++ b/src/cairo-surface.c
@@ -2764,6 +2764,7 @@ _cairo_surface_create_in_error (cairo_status_t status)
     case CAIRO_STATUS_PNG_ERROR:
     case CAIRO_STATUS_FREETYPE_ERROR:
     case CAIRO_STATUS_WIN32_GDI_ERROR:
+    case CAIRO_STATUS_TAG_ERROR:
     default:
 	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 	return (cairo_surface_t *) &_cairo_surface_nil;
diff --git a/src/cairo-tag-attributes-private.h b/src/cairo-tag-attributes-private.h
new file mode 100644
index 000000000..69fd24640
--- /dev/null
+++ b/src/cairo-tag-attributes-private.h
@@ -0,0 +1,73 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2016 Adrian Johnson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Adrian Johnson.
+ *
+ * Contributor(s):
+ *	Adrian Johnson <ajohnson@redneon.com>
+ */
+
+#ifndef CAIRO_TAG_ATTRIBUTES_PRIVATE_H
+#define CAIRO_TAG_ATTRIBUTES_PRIVATE_H
+
+typedef enum {
+    TAG_LINK_INVALID = 0,
+    TAG_LINK_EMPTY,
+    TAG_LINK_DEST,
+    TAG_LINK_URI,
+    TAG_LINK_FILE,
+} cairo_tag_link_type_t;
+
+typedef struct _cairo_link_attrs {
+    cairo_tag_link_type_t link_type;
+    cairo_array_t rects; /* array of cairo_rectangle_t */
+    char *dest;
+    char *uri;
+    char *file;
+    int page;
+    cairo_point_double_t pos;
+} cairo_link_attrs_t;
+
+typedef struct _cairo_dest_attrs {
+    char *name;
+    double x;
+    double y;
+    cairo_bool_t x_valid;
+    cairo_bool_t y_valid;
+    cairo_bool_t internal;
+} cairo_dest_attrs_t;
+
+cairo_private cairo_int_status_t
+_cairo_tag_parse_link_attributes (const char *attributes, cairo_link_attrs_t *link_attrs);
+
+cairo_private cairo_int_status_t
+_cairo_tag_parse_dest_attributes (const char *attributes, cairo_dest_attrs_t *dest_attrs);
+
+#endif /* CAIRO_TAG_ATTRIBUTES_PRIVATE_H */
diff --git a/src/cairo-tag-attributes.c b/src/cairo-tag-attributes.c
new file mode 100644
index 000000000..53433082c
--- /dev/null
+++ b/src/cairo-tag-attributes.c
@@ -0,0 +1,570 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2016 Adrian Johnson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Adrian Johnson.
+ *
+ * Contributor(s):
+ *	Adrian Johnson <ajohnson@redneon.com>
+ */
+
+#include "cairoint.h"
+
+#include "cairo-array-private.h"
+#include "cairo-list-inline.h"
+#include "cairo-tag-attributes-private.h"
+
+#include <string.h>
+
+typedef enum {
+    ATTRIBUTE_BOOL,  /* Either true/false or 1/0 may be used. */
+    ATTRIBUTE_INT,
+    ATTRIBUTE_FLOAT, /* Decimal separator is in current locale. */
+    ATTRIBUTE_STRING, /* Enclose in single quotes. String escapes:
+                       *   \'  - single quote
+                       *   \\  - backslash
+                       */
+} attribute_type_t;
+
+typedef struct _attribute_spec {
+    const char *name;
+    attribute_type_t type;
+    int array_size; /* 0 = scalar, -1 = variable size array */
+} attribute_spec_t;
+
+/*
+ * name [required] Unique name of this destination (UTF-8)
+ * x    [optional] x coordinate of destination on page. Default is x coord of
+ *                 extents of operations enclosed by the dest begin/end tags.
+ * y    [optional] y coordinate of destination on page. Default is y coord of
+ *                 extents of operations enclosed by the dest begin/end tags.
+ * internal [optional] If true, the name may be optimized out of the PDF where
+ *                     possible. Default false.
+ */
+static attribute_spec_t _dest_attrib_spec[] = {
+    { "name",     ATTRIBUTE_STRING },
+    { "x",        ATTRIBUTE_FLOAT },
+    { "y",        ATTRIBUTE_FLOAT },
+    { "internal", ATTRIBUTE_BOOL },
+    { NULL }
+};
+
+/*
+ * rect [optional] One or more rectangles to define link region. Default
+ *                 is the extents of the operations enclosed by the link begin/end tags.
+ *                 Each rectangle is specified by four array elements: x, y, width, height.
+ *                 ie the array size must be a multiple of four.
+ *
+ * Internal Links
+ * --------------
+ * either:
+ *   dest - name of dest tag in the PDF file to link to (UTF8)
+ * or
+ *   page - Page number in the PDF file to link to
+ *   pos  - [optional] Position of destination on page. Default is 0,0.
+ *
+ * URI Links
+ * ---------
+ * uri [required] Uniform resource identifier (ASCII).
+
+ * File Links
+ * ----------
+ * file - [required] File name of PDF file to link to.
+ *   either:
+ *     dest - name of dest tag in the PDF file to link to (UTF8)
+ *   or
+ *     page - Page number in the PDF file to link to
+ *     pos  - [optional] Position of destination on page. Default is 0,0.
+ */
+static attribute_spec_t _link_attrib_spec[] =
+{
+    { "rect", ATTRIBUTE_FLOAT, -1 },
+    { "dest", ATTRIBUTE_STRING },
+    { "uri",  ATTRIBUTE_STRING },
+    { "file", ATTRIBUTE_STRING },
+    { "page", ATTRIBUTE_INT },
+    { "pos",  ATTRIBUTE_FLOAT, 2 },
+    { NULL }
+};
+
+typedef union {
+    cairo_bool_t b;
+    int i;
+    double f;
+    char *s;
+} attrib_val_t;
+
+typedef struct _attribute {
+    char *name;
+    attribute_type_t type;
+    int array_len; /* 0 = scalar */
+    attrib_val_t scalar;
+    cairo_array_t array; /* array of attrib_val_t */
+    cairo_list_t link;
+} attribute_t;
+
+static const char *
+skip_space (const char *p)
+{
+    while (_cairo_isspace (*p))
+	p++;
+
+    return p;
+}
+
+static const char *
+parse_bool (const char *p, cairo_bool_t *b)
+{
+    if (*p == '1') {
+	*b = TRUE;
+	return p + 1;
+    } else if (*p == '0') {
+	*b = FALSE;
+	return p + 1;
+    } else if (strcmp (p, "true") == 0) {
+	*b = TRUE;
+	return p + 4;
+    } else if (strcmp (p, "false") == 0) {
+	*b = FALSE;
+	return p + 5;
+    }
+
+    return NULL;
+}
+
+static const char *
+parse_int (const char *p, int *i)
+{
+    int n;
+
+    if (sscanf(p, "%d%n", i, &n) > 0)
+	return p + n;
+
+    return NULL;
+}
+
+static const char *
+parse_float (const char *p, double *d)
+{
+    int n;
+
+    if (sscanf(p, "%lf%n", d, &n) > 0)
+	return p + n;
+
+    return NULL;
+}
+
+static const char *
+decode_string (const char *p, int *len, char *s)
+{
+    if (*p != '\'')
+	return NULL;
+
+    p++;
+    if (! *p)
+	return NULL;
+
+    *len = 0;
+    while (*p) {
+	if (*p == '\\') {
+	    p++;
+	    if (*p) {
+		if (s)
+		    *s++ = *p;
+		p++;
+		(*len)++;
+	    }
+	} else if (*p == '\'') {
+	    return p + 1;
+	} else {
+	    if (s)
+		*s++ = *p;
+	    p++;
+	    (*len)++;
+	}
+    }
+
+    return NULL;
+}
+
+static const char *
+parse_string (const char *p, char **s)
+{
+    const char *end;
+    int len;
+
+    end = decode_string (p, &len, NULL);
+    if (!end)
+	return NULL;
+
+    *s = malloc (len + 1);
+    decode_string (p, &len, *s);
+    (*s)[len] = 0;
+
+    return end;
+}
+
+static const char *
+parse_scalar (const char *p, attribute_type_t type, attrib_val_t *scalar)
+{
+    switch (type) {
+	case ATTRIBUTE_BOOL:
+	    return parse_bool (p, &scalar->b);
+	case ATTRIBUTE_INT:
+	    return parse_int (p, &scalar->i);
+	case ATTRIBUTE_FLOAT:
+	    return parse_float (p, &scalar->f);
+	case ATTRIBUTE_STRING:
+	    return parse_string (p, &scalar->s);
+    }
+
+    return NULL;
+}
+
+static cairo_int_status_t
+parse_array (const char *p, attribute_type_t type, cairo_array_t *array, const char **end)
+{
+    attrib_val_t val;
+    cairo_int_status_t status;
+
+    p = skip_space (p);
+    if (! *p)
+	return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+    if (*p++ != '[')
+	return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+    while (TRUE) {
+	p = skip_space (p);
+	if (! *p)
+	    return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+	if (*p == ']') {
+	    *end = p + 1;
+	    return CAIRO_INT_STATUS_SUCCESS;
+	}
+
+	p = parse_scalar (p, type, &val);
+	if (!p)
+	    return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+	status = _cairo_array_append (array, &val);
+	if (unlikely (status))
+	    return status;
+    }
+
+    return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+}
+
+static cairo_int_status_t
+parse_name (const char *p, const char **end, char **s)
+{
+    const char *p2;
+    char *name;
+    int len;
+
+    if (! _cairo_isalpha (*p))
+	return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+    p2 = p;
+    while (_cairo_isalpha (*p2) || _cairo_isdigit (*p2))
+	p2++;
+
+    len = p2 - p;
+    name = malloc (len + 1);
+    if (unlikely (name == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    memcpy (name, p, len);
+    name[len] = 0;
+    *s = name;
+    *end = p2;
+
+    return CAIRO_INT_STATUS_SUCCESS;
+}
+
+static cairo_int_status_t
+parse_attributes (const char *attributes, attribute_spec_t *attrib_def, cairo_list_t *list)
+{
+    attribute_spec_t *def;
+    attribute_t *attrib;
+    char *name;
+    cairo_int_status_t status;
+    const char *p = attributes;
+
+    if (! p)
+	return _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+    while (*p) {
+	p = skip_space (p);
+	if (! *p)
+	    break;
+
+	status = parse_name (p, &p, &name);
+	if (status)
+	    return status;
+
+	def = attrib_def;
+	while (def->name) {
+	    if (strcmp (name, def->name) == 0)
+		break;
+	    def++;
+	}
+	if (! def->name) {
+	    status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+	    goto fail1;
+	}
+
+	attrib = calloc (1, sizeof (attribute_t));
+	if (unlikely (attrib == NULL)) {
+	    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+	    goto fail1;
+	}
+
+	attrib->name = name;
+	attrib->type = def->type;
+	_cairo_array_init (&attrib->array, sizeof(attrib_val_t));
+
+	p = skip_space (p);
+	if (def->type == ATTRIBUTE_BOOL && *p != '=') {
+	    attrib->scalar.b = TRUE;
+	} else {
+	    if (*p++ != '=') {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto fail2;
+	    }
+
+	    if (def->array_size == 0) {
+		p = parse_scalar (p, def->type, &attrib->scalar);
+		if (!p) {
+		    status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		    goto fail2;
+		}
+
+		attrib->array_len = 0;
+	    } else {
+		status = parse_array (p, def->type, &attrib->array, &p);
+		if (unlikely (status))
+		    goto fail2;
+
+		attrib->array_len = _cairo_array_num_elements (&attrib->array);
+		if (def->array_size > 0 && attrib->array_len != def->array_size) {
+		    status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		    goto fail2;
+		}
+	    }
+	}
+
+	cairo_list_add_tail (&attrib->link, list);
+    }
+
+    return CAIRO_INT_STATUS_SUCCESS;
+
+  fail2:
+    _cairo_array_fini (&attrib->array);
+    free (attrib);
+  fail1:
+    free (name);
+
+    return status;
+}
+
+static void
+free_attributes_list (cairo_list_t *list)
+{
+    attribute_t *attr, *next;
+
+    cairo_list_foreach_entry_safe (attr, next, attribute_t, list, link)
+    {
+	cairo_list_del (&attr->link);
+	free (attr->name);
+	_cairo_array_fini (&attr->array);
+	free (attr);
+    }
+}
+
+static attribute_t *
+find_attribute (cairo_list_t *list, const char *name)
+{
+    attribute_t *attr;
+
+    cairo_list_foreach_entry (attr, attribute_t, list, link)
+    {
+	if (strcmp (attr->name, name) == 0)
+	    return attr;
+    }
+
+    return NULL;
+}
+
+cairo_int_status_t
+_cairo_tag_parse_link_attributes (const char *attributes, cairo_link_attrs_t *link_attrs)
+{
+    cairo_list_t list;
+    cairo_int_status_t status;
+    attribute_t *attr;
+    attrib_val_t val;
+
+    cairo_list_init (&list);
+    status = parse_attributes (attributes, _link_attrib_spec, &list);
+    if (unlikely (status))
+	return status;
+
+    memset (link_attrs, 0, sizeof (cairo_link_attrs_t));
+    _cairo_array_init (&link_attrs->rects, sizeof (cairo_rectangle_t));
+    if (find_attribute (&list, "uri")) {
+	link_attrs->link_type = TAG_LINK_URI;
+    } else if (find_attribute (&list, "file")) {
+	link_attrs->link_type = TAG_LINK_FILE;
+    } else if (find_attribute (&list, "dest")) {
+	link_attrs->link_type = TAG_LINK_DEST;
+    } else if (find_attribute (&list, "page")) {
+	link_attrs->link_type = TAG_LINK_DEST;
+    } else {
+	link_attrs->link_type = TAG_LINK_EMPTY;
+	goto cleanup;
+    }
+
+    cairo_list_foreach_entry (attr, attribute_t, &list, link)
+    {
+	if (strcmp (attr->name, "uri") == 0) {
+	    if (link_attrs->link_type != TAG_LINK_URI) {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto cleanup;
+	    }
+
+	    link_attrs->uri = strdup (attr->scalar.s);
+	} else if (strcmp (attr->name, "file") == 0) {
+	    if (link_attrs->link_type != TAG_LINK_FILE) {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto cleanup;
+	    }
+
+	    link_attrs->file = strdup (attr->scalar.s);
+	} else if (strcmp (attr->name, "dest") == 0) {
+	    if (! (link_attrs->link_type == TAG_LINK_DEST ||
+		   link_attrs->link_type != TAG_LINK_FILE)) {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto cleanup;
+	    }
+
+	    link_attrs->dest = strdup (attr->scalar.s);
+	} else if (strcmp (attr->name, "page") == 0) {
+	    if (! (link_attrs->link_type == TAG_LINK_DEST ||
+		   link_attrs->link_type != TAG_LINK_FILE)) {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto cleanup;
+	    }
+
+	    link_attrs->page = attr->scalar.i;
+
+	} else if (strcmp (attr->name, "pos") == 0) {
+	    if (! (link_attrs->link_type == TAG_LINK_DEST ||
+		   link_attrs->link_type != TAG_LINK_FILE)) {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto cleanup;
+	    }
+
+	    _cairo_array_copy_element (&attr->array, 0, &val);
+	    link_attrs->pos.x = val.f;
+	    _cairo_array_copy_element (&attr->array, 1, &val);
+	    link_attrs->pos.y = val.f;
+	} else if (strcmp (attr->name, "rect") == 0) {
+	    cairo_rectangle_t rect;
+	    int i;
+	    int num_elem = _cairo_array_num_elements (&attr->array);
+	    if (num_elem == 0 || num_elem % 4 != 0) {
+		status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+		goto cleanup;
+	    }
+
+	    for (i = 0; i < num_elem; i += 4) {
+		_cairo_array_copy_element (&attr->array, i, &val);
+		rect.x = val.f;
+		_cairo_array_copy_element (&attr->array, i+1, &val);
+		rect.y = val.f;
+		_cairo_array_copy_element (&attr->array, i+2, &val);
+		rect.width = val.f;
+		_cairo_array_copy_element (&attr->array, i+3, &val);
+		rect.height = val.f;
+		status = _cairo_array_append (&link_attrs->rects, &rect);
+		if (unlikely (status))
+		    goto cleanup;
+	    }
+	}
+    }
+
+  cleanup:
+    free_attributes_list (&list);
+    if (unlikely (status)) {
+	free (link_attrs->dest);
+	free (link_attrs->uri);
+	free (link_attrs->file);
+	_cairo_array_fini (&link_attrs->rects);
+    }
+
+    return status;
+}
+
+cairo_int_status_t
+_cairo_tag_parse_dest_attributes (const char *attributes, cairo_dest_attrs_t *dest_attrs)
+{
+    cairo_list_t list;
+    cairo_int_status_t status;
+    attribute_t *attr;
+
+    memset (dest_attrs, 0, sizeof (cairo_dest_attrs_t));
+    cairo_list_init (&list);
+    status = parse_attributes (attributes, _dest_attrib_spec, &list);
+    if (unlikely (status))
+	goto cleanup;
+
+    cairo_list_foreach_entry (attr, attribute_t, &list, link)
+    {
+	if (strcmp (attr->name, "name") == 0) {
+	    dest_attrs->name = strdup (attr->scalar.s);
+	} else if (strcmp (attr->name, "x") == 0) {
+	    dest_attrs->x = attr->scalar.f;
+	    dest_attrs->x_valid = TRUE;
+	} else if (strcmp (attr->name, "y") == 0) {
+	    dest_attrs->y = attr->scalar.f;
+	    dest_attrs->y_valid = TRUE;
+	} else if (strcmp (attr->name, "internal") == 0) {
+	    dest_attrs->internal = attr->scalar.b;
+	}
+    }
+
+    if (! dest_attrs->name)
+	status = _cairo_error (CAIRO_INT_STATUS_TAG_ERROR);
+
+  cleanup:
+    free_attributes_list (&list);
+
+    return status;
+}
diff --git a/src/cairo-tag-stack-private.h b/src/cairo-tag-stack-private.h
new file mode 100644
index 000000000..9528cb4f6
--- /dev/null
+++ b/src/cairo-tag-stack-private.h
@@ -0,0 +1,106 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2016 Adrian Johnson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Adrian Johnson.
+ *
+ * Contributor(s):
+ *	Adrian Johnson <ajohnson@redneon.com>
+ */
+
+#ifndef CAIRO_TAG_STACK_PRIVATE_H
+#define CAIRO_TAG_STACK_PRIVATE_H
+
+#include "cairo-list-inline.h"
+
+/* The type of a single tag */
+typedef enum {
+    TAG_TYPE_INVALID = 0,
+    TAG_TYPE_STRUCTURE = 1,
+    TAG_TYPE_LINK = 2,
+    TAG_TYPE_DEST = 4,
+} cairo_tag_type_t;
+
+/* The type of the structure tree. */
+typedef enum _cairo_tag_stack_structure_type {
+    TAG_TREE_TYPE_TAGGED, /* compliant with Tagged PDF */
+    TAG_TREE_TYPE_STRUCTURE, /* valid structure but not 'Tagged PDF' compliant */
+    TAG_TREE_TYPE_LINK_ONLY, /* contains Link tags only */
+    TAG_TREE_TYPE_NO_TAGS, /* no tags used */
+    TAG_TREE_TYPE_INVALID, /* invalid tag structure */
+} cairo_tag_stack_structure_type_t;
+
+typedef struct _cairo_tag_stack_elem {
+    char *name;
+    char *attributes;
+    void *data;
+    cairo_list_t link;
+
+} cairo_tag_stack_elem_t;
+
+typedef struct _cairo_tag_stack {
+    cairo_list_t list;
+    cairo_tag_stack_structure_type_t type;
+    int size;
+
+} cairo_tag_stack_t;
+
+cairo_private void
+_cairo_tag_stack_init (cairo_tag_stack_t *stack);
+
+cairo_private void
+_cairo_tag_stack_fini (cairo_tag_stack_t *stack);
+
+cairo_private cairo_tag_stack_structure_type_t
+_cairo_tag_stack_get_structure_type (cairo_tag_stack_t *stack);
+
+cairo_private cairo_int_status_t
+_cairo_tag_stack_push (cairo_tag_stack_t *stack,
+		       const char        *name,
+		       const char        *attributes);
+
+cairo_private void
+_cairo_tag_stack_set_top_data (cairo_tag_stack_t *stack,
+			       void              *data);
+
+cairo_private cairo_int_status_t
+_cairo_tag_stack_pop (cairo_tag_stack_t *stack,
+		      const char *name,
+		      cairo_tag_stack_elem_t **elem);
+
+cairo_private cairo_tag_stack_elem_t *
+_cairo_tag_stack_top_elem (cairo_tag_stack_t *stack);
+
+cairo_private void
+_cairo_tag_stack_free_elem (cairo_tag_stack_elem_t *elem);
+
+cairo_private cairo_tag_type_t
+_cairo_tag_get_type (const char *name);
+
+#endif /* CAIRO_TAG_STACK_PRIVATE_H */
diff --git a/src/cairo-tag-stack.c b/src/cairo-tag-stack.c
new file mode 100644
index 000000000..858221eb2
--- /dev/null
+++ b/src/cairo-tag-stack.c
@@ -0,0 +1,279 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2016 Adrian Johnson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Adrian Johnson.
+ *
+ * Contributor(s):
+ *	Adrian Johnson <ajohnson@redneon.com>
+ */
+
+#include "cairoint.h"
+
+#include "cairo-tag-stack-private.h"
+
+/* Tagged PDF must have one of these tags at the top level */
+static const char * _cairo_tag_stack_tagged_pdf_top_level_element_list[] =
+{
+    "Document",
+    "Part",
+    "Art",
+    "Sect",
+    "Div",
+    NULL
+};
+
+/* List of valid tag names. Table numbers reference PDF 32000 */
+static const char * _cairo_tag_stack_struct_pdf_list[] =
+{
+    /* Table 333 - Grouping Elements */
+    "Document",
+    "Part",
+    "Art",
+    "Sect",
+    "Div",
+    "BlockQuote",
+    "Caption",
+    "TOC",
+    "TOCI",
+    "Index",
+    "NonStruct",
+    "Private",
+
+    /* Table 335 - Standard structure types for paragraphlike elements */
+    "P", "H",
+    "H1", "H2", "H3", "H4", "H5", "H6",
+
+    /* Table 336 - Standard structure types for list elements */
+    "L", "LI", "Lbl", "LBody",
+
+    /* Table 337 - Standard structure types for table elements */
+    "Table",
+    "TR", "TH", "TD",
+    "THead", "TBody", "TFoot",
+
+    /* Table 338 - Standard structure types for inline-level structure elements */
+    "Span",
+    "Quote",
+    "Note",
+    "Reference",
+    "BibEntry",
+    "Code",
+    "Link", /* CAIRO_TAG_LINK */
+    "Annot",
+    "Ruby",
+    "Warichu",
+
+    /* Table 339 - Standard structure types for Ruby and Warichu elements */
+    "RB", "RT", "RP",
+    "WT", "WP",
+
+    /* Table 340 - Standard structure types for illustration elements */
+    "Figure",
+    "Formula",
+    "Form",
+
+    NULL
+};
+
+/* List of cairo specific tag names */
+static const char * _cairo_tag_stack_cairo_tag_list[] =
+{
+    CAIRO_TAG_DEST,
+    NULL
+};
+
+void
+_cairo_tag_stack_init (cairo_tag_stack_t *stack)
+{
+    cairo_list_init (&stack->list);
+    stack->type = TAG_TREE_TYPE_NO_TAGS;
+    stack->size = 0;
+}
+
+void
+_cairo_tag_stack_fini (cairo_tag_stack_t *stack)
+{
+    while (! cairo_list_is_empty (&stack->list)) {
+	cairo_tag_stack_elem_t *elem;
+
+	elem = cairo_list_first_entry (&stack->list, cairo_tag_stack_elem_t, link);
+	cairo_list_del (&elem->link);
+	free (elem->name);
+	free (elem->attributes);
+	free (elem);
+    }
+}
+
+cairo_tag_stack_structure_type_t
+_cairo_tag_stack_get_structure_type (cairo_tag_stack_t *stack)
+{
+    return stack->type;
+}
+
+static cairo_bool_t
+name_in_list (const char *name, const char **list)
+{
+    if (! name)
+	return FALSE;
+
+    while (*list) {
+	if (strcmp (name, *list) == 0)
+	    return TRUE;
+	list++;
+    }
+
+    return FALSE;
+}
+
+cairo_int_status_t
+_cairo_tag_stack_push (cairo_tag_stack_t *stack,
+		       const char        *name,
+		       const char        *attributes)
+{
+    cairo_tag_stack_elem_t *elem;
+
+    if (! name_in_list (name, _cairo_tag_stack_struct_pdf_list) &&
+	! name_in_list (name, _cairo_tag_stack_cairo_tag_list))
+    {
+	stack->type = TAG_TYPE_INVALID;
+	return _cairo_error (CAIRO_STATUS_TAG_ERROR);
+    }
+
+    if (stack->type == TAG_TREE_TYPE_NO_TAGS) {
+	if (name_in_list (name, _cairo_tag_stack_tagged_pdf_top_level_element_list))
+	    stack->type = TAG_TREE_TYPE_TAGGED;
+	else if (strcmp (name, "Link") == 0)
+	    stack->type = TAG_TREE_TYPE_LINK_ONLY;
+	else if (name_in_list (name, _cairo_tag_stack_struct_pdf_list))
+	    stack->type = TAG_TREE_TYPE_STRUCTURE;
+    } else {
+	if (stack->type == TAG_TREE_TYPE_LINK_ONLY &&
+	    name_in_list (name, _cairo_tag_stack_struct_pdf_list))
+	{
+	    stack->type = TAG_TREE_TYPE_STRUCTURE;
+	}
+    }
+
+    elem = malloc (sizeof(cairo_tag_stack_elem_t));
+    if (unlikely (elem == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    elem->name = strdup (name);
+    if (unlikely (elem->name == NULL))
+	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+    if (attributes) {
+	elem->attributes = strdup (attributes);
+	if (unlikely (elem->attributes == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    } else {
+	elem->attributes = NULL;
+    }
+
+    elem->data = NULL;
+
+    cairo_list_add_tail (&elem->link, &stack->list);
+    stack->size++;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_private void
+_cairo_tag_stack_set_top_data (cairo_tag_stack_t *stack,
+			       void        *data)
+{
+    cairo_tag_stack_elem_t *top;
+
+    top = _cairo_tag_stack_top_elem (stack);
+    if (top)
+	top->data = data;
+}
+
+cairo_int_status_t
+_cairo_tag_stack_pop (cairo_tag_stack_t *stack,
+		      const char *name,
+		      cairo_tag_stack_elem_t **elem)
+{
+    cairo_tag_stack_elem_t *top;
+
+    top = _cairo_tag_stack_top_elem (stack);
+    if (!top) {
+	stack->type = TAG_TYPE_INVALID;
+	return _cairo_error (CAIRO_STATUS_TAG_ERROR);
+    }
+
+    cairo_list_del (&top->link);
+    stack->size--;
+    if (strcmp (top->name, name) != 0) {
+	stack->type = TAG_TYPE_INVALID;
+	_cairo_tag_stack_free_elem (top);
+	return _cairo_error (CAIRO_STATUS_TAG_ERROR);
+    }
+
+    if (elem)
+	*elem = top;
+    else
+	_cairo_tag_stack_free_elem (top);
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_tag_stack_elem_t *
+_cairo_tag_stack_top_elem (cairo_tag_stack_t *stack)
+{
+    if (cairo_list_is_empty (&stack->list))
+	return NULL;
+
+    return cairo_list_last_entry (&stack->list, cairo_tag_stack_elem_t, link);
+}
+
+void
+_cairo_tag_stack_free_elem (cairo_tag_stack_elem_t *elem)
+{
+    free (elem->name);
+    free (elem->attributes);
+    free (elem);
+}
+
+cairo_tag_type_t
+_cairo_tag_get_type (const char *name)
+{
+    if (! name_in_list (name, _cairo_tag_stack_struct_pdf_list) &&
+	! name_in_list (name, _cairo_tag_stack_cairo_tag_list))
+	return TAG_TYPE_INVALID;
+
+    if (strcmp(name, "Link") == 0)
+	return (TAG_TYPE_LINK | TAG_TYPE_STRUCTURE);
+
+    if (strcmp(name, "cairo.dest") == 0)
+	return TAG_TYPE_DEST;
+
+    return TAG_TYPE_STRUCTURE;
+}
diff --git a/src/cairo.c b/src/cairo.c
index 76d8c56ce..02b917102 100644
--- a/src/cairo.c
+++ b/src/cairo.c
@@ -107,6 +107,220 @@
  * space</firstterm>.
  **/
 
+/**
+ * SECTION:cairo-tag
+ * @Title: Tags and Links
+ * @Short_Description: Hyperlinks and document structure
+ * @See_Also: #cairo_pdf_surface_t
+ *
+ * The tag functions provide the ability to specify hyperlinks and
+ * document logical structure on supported backends. The following tags are supported:
+ * * [Link][link] - Create a hyperlink
+ * * [Destinations][dest] - Create a hyperlink destination
+ * * [Document Structure Tags][doc-struct] - Create PDF Document Structure
+ *
+ * # Link Tags # {#link}
+ * A hyperlink is specified by enclosing the hyperlink text with the %CAIRO_TAG_LINK tag.
+ *
+ * For example:
+ * <informalexample><programlisting>
+ * cairo_tag_begin (cr, CAIRO_TAG_LINK, "uri='http://cairographics.org'");
+ * cairo_move_to (cr, 50, 50);
+ * cairo_show_text (cr, "This is a link to the cairo website.");
+ * cairo_tag_end (cr, CAIRO_TAG_LINK);
+ * </programlisting></informalexample>
+ *
+ * The PDF backend uses one or more rectangles to define the clickable
+ * area of the link.  By default cairo will use the extents of the
+ * drawing operations enclosed by the begin/end link tags to define the
+ * clickable area. In some cases, such as a link split across two
+ * lines, the default rectangle is undesirable.
+ *
+ * @rect: [optional] The "rect" attribute allows the application to
+ * specify one or more rectangles that form the clickable region.  The
+ * value of this attribute is an array of floats. Each rectangle is
+ * specified by four elements in the array: x, y, width, height. The
+ * array size must be a multiple of four.
+ *
+ * An example of creating a link with user specified clickable region:
+ * <informalexample><programlisting>
+ * cairo_font_extents_t font_extents;
+ * cairo_text_extents_t text1_extents;
+ * cairo_text_extents_t text2_extents;
+ * char attribs[100];
+ * const char *text1 = "This link is split";
+ * const char *text2 = "across two lines";
+ *
+ * cairo_font_extents (cr, &font_extents);
+ * cairo_move_to (cr, 450, 50);
+ * cairo_text_extents (cr, text1, &text1_extents);
+ * cairo_move_to (cr, 50, 70);
+ * cairo_text_extents (cr, text2, &text2_extents);
+ * sprintf (attribs,
+ *          "rect=[%f %f %f %f %f %f %f %f] uri='http://cairographics.org'",
+ *          text1_extents.x_bearing,
+ *          text1_extents.y_bearing,
+ *          text1_extents.width,
+ *          text1_extents.height,
+ *          text2_extents.x_bearing,
+ *          text2_extents.y_bearing,
+ *          text2_extents.width,
+ *          text2_extents.height);
+ *
+ * cairo_tag_begin (cr, CAIRO_TAG_LINK, attribs);
+ * cairo_show_text (cr, "This is a link to the cairo website");
+ * cairo_move_to (cr, 450, 50);
+ * cairo_show_text (cr, text1);
+ * cairo_move_to (cr, 50, 70);
+ * cairo_show_text (cr, text2);
+ * cairo_tag_end (cr, CAIRO_TAG_LINK);
+ * </programlisting></informalexample>
+ *
+ * There are three types of links. Each type has its own attributes as detailed below.
+ * * [Internal Links][internal-link] - A link to a location in the same document
+ * * [URI Links][uri-link] - A link to a Uniform resource identifier
+ * * [File Links][file-link] - A link to a location in another document
+ *
+ * ## Internal Links ## {#internal-link}
+ * An internal link is a link to a location in the same document. The destination
+ * is specified with either:
+ *
+ * @dest: a UTF-8 string specifying the destination in the PDF file to link
+ * to. Destinations are created with the %CAIRO_TAG_DEST tag.
+ *
+ * or the two attributes:
+ *
+ * @page: An integer specifying the page number in the PDF file to link to.
+ *
+ * @pos: [optional] An array of two floats specifying the x,y position
+ * on the page. Default is 0,0.
+ *
+ * An example of the link attributes to link to a page and x,y position:
+ * <programlisting>
+ * "page=3 pos=[3.1 6.2]"
+ * </programlisting>
+ *
+ * ## URI Links ## {#uri-link}
+ * A URI link is a link to a Uniform Resource Identifier ([RFC 2396](http://tools.ietf.org/html/rfc2396)).
+ *
+ * A URI is specified with the following attribute:
+ *
+ * @uri: An ASCII string specifying the URI.
+ *
+ * An example of the link attributes to the cairo website:
+ * <programlisting>
+ * "uri='http://cairographics.org'"
+ * </programlisting>
+ *
+ * ## File Links ## {#file-link}
+ * A file link is a link a location in another PDF file.
+ *
+ * The file attribute (required) specifies the name of the PDF file:
+ *
+ * @file: File name of PDF file to link to.
+ *
+ * The position is specified by either:
+ *
+ *  @dest: a UTF-8 string specifying the named destination in the PDF file.
+ *
+ * or
+ *
+ *  @page: An integer specifying the page number in the PDF file.
+ *
+ *  @pos: [optional] An array of two floats specifying the x,y position
+ *  on the page. Default is 0,0.
+ *
+ * An example of the link attributes to PDF file:
+ * <programlisting>
+ * "file='document.pdf' page=16 pos=[25 40]"
+ * </programlisting>
+ *
+ * # Destination Tags # {#dest}
+
+ * A destination is specified by enclosing the destination drawing
+ * operations with the %CAIRO_TAG_DEST tag.
+ *
+ * @name: [required] A UTF-8 string specifying the name of this destination.
+ *
+ * @x: [optional] A float specifying the x coordinate of destination
+ *                 position on this page. If not specified the default
+ *                 x coordinate is the left side of the extents of the
+ *                 operations enclosed by the %CAIRO_TAG_DEST begin/end tags. If
+ *                 no operations are enclosed, the x coordidate is 0.
+ *
+ * @y: [optional] A float specifying the y coordinate of destination
+ *                 position on this page. If not specified the default
+ *                 y coordinate is the top of the extents of the
+ *                 operations enclosed by the %CAIRO_TAG_DEST begin/end tags. If
+ *                 no operations are enclosed, the y coordidate is 0.
+ *
+ * @internal: A boolean that if true, the destination name may be
+ *            ommitted from PDF where possible. In this case, links
+ *            refer directly to the page and position instead of via
+ *            the named destination table. Note that if this
+ *            destination is referenced by another PDF (see [File Links][file-link]),
+ *            this attribute must be false. Default is false.
+ *
+ * <informalexample><programlisting>
+ * /&ast; Create a hyperlink &ast;/
+ * cairo_tag_begin (cr, CAIRO_TAG_LINK, "dest='mydest' internal");
+ * cairo_move_to (cr, 50, 50);
+ * cairo_show_text (cr, "This is a hyperlink.");
+ * cairo_tag_end (cr, CAIRO_TAG_LINK);
+ *
+ * /&ast; Create a destination &ast;/
+ * cairo_tag_begin (cr, CAIRO_TAG_DEST, "name='mydest'");
+ * cairo_move_to (cr, 50, 250);
+ * cairo_show_text (cr, "This paragraph is the destination of the above link.");
+ * cairo_tag_end (cr, CAIRO_TAG_DEST);
+ * </programlisting></informalexample>
+ *
+ * # Document Structure (PDF) # {#doc-struct}
+ *
+ * The document structure tags provide a means of specifying structural information
+ * such as headers, paragraphs, tables, and figures. The inclusion of structural information faciliates:
+ * * Extraction of text and graphics for copy and paste
+ * * Reflow of text and graphics in the viewer
+ * * Proccessing text eg searching and indexing
+ * * Conversion to other formats
+ * * Accessability support
+ *
+ * The list of structure types is specified in section 14.8.4 of the
+ * [PDF Reference](http://www.adobe.com/content/dam/Adobe/en/devnet/acrobat/pdfs/PDF32000_2008.pdf).
+ *
+ * Note the PDF "Link" structure tag is the same as the cairo %CAIRO_TAG_LINK tag.
+ *
+ * The following example creates a document structure for a document containing two section, each with
+ * a header and a paragraph.
+ *
+ * <informalexample><programlisting>
+ * cairo_tag_begin (cr, "Document", NULL);
+ *
+ * cairo_tag_begin (cr, "Sect", NULL);
+ * cairo_tag_begin (cr, "H1", NULL);
+ * cairo_show_text (cr, "Heading 1");
+ * cairo_tag_end (cr, "H1");
+ *
+ * cairo_tag_begin (cr, "P", NULL);
+ * cairo_show_text (cr, "Paragraph 1");
+ * cairo_tag_end (cr, "P");
+ * cairo_tag_end (cr, "Sect");
+ *
+ * cairo_tag_begin (cr, "Sect", NULL);
+ * cairo_tag_begin (cr, "H1", NULL);
+ * cairo_show_text (cr, "Heading 2");
+ * cairo_tag_end (cr, "H1");
+ *
+ * cairo_tag_begin (cr, "P", NULL);
+ * cairo_show_text (cr, "Paragraph 2");
+ * cairo_tag_end (cr, "P");
+ * cairo_tag_end (cr, "Sect");
+ *
+ * cairo_tag_end (cr, "Document");
+ * </programlisting></informalexample>
+ *
+ **/
+
 #define DEFINE_NIL_CONTEXT(status)					\
     {									\
 	CAIRO_REFERENCE_COUNT_INVALID,	/* ref_count */			\
@@ -156,7 +370,8 @@ static const cairo_t _cairo_nil[] = {
     DEFINE_NIL_CONTEXT (CAIRO_STATUS_JBIG2_GLOBAL_MISSING),
     DEFINE_NIL_CONTEXT (CAIRO_STATUS_PNG_ERROR),
     DEFINE_NIL_CONTEXT (CAIRO_STATUS_FREETYPE_ERROR),
-    DEFINE_NIL_CONTEXT (CAIRO_STATUS_WIN32_GDI_ERROR)
+    DEFINE_NIL_CONTEXT (CAIRO_STATUS_WIN32_GDI_ERROR),
+    DEFINE_NIL_CONTEXT (CAIRO_STATUS_TAG_ERROR)
 
 };
 COMPILE_TIME_ASSERT (ARRAY_LENGTH (_cairo_nil) == CAIRO_STATUS_LAST_STATUS - 1);
@@ -2667,6 +2882,24 @@ cairo_copy_clip_rectangle_list (cairo_t *cr)
 }
 
 /**
+ * CAIRO_TAG_DEST:
+ *
+ * Create a destination for a hyperlink. Destination tag attributes
+ * are detailed at [Destinations][dests].
+ *
+ * Since: 1.16
+ **/
+
+/**
+ * CAIRO_TAG_LINK:
+ *
+ * Create hyperlink. Link tag attributes are detailed at
+ * [Links][links].
+ *
+ * Since: 1.16
+ **/
+
+/**
  * cairo_tag_begin:
  * @cr: a cairo context
  * @tag_name: tag name
@@ -2676,6 +2909,30 @@ cairo_copy_clip_rectangle_list (cairo_t *cr)
  * cairo_tag_end() with the same @tag_name to mark the end of the
  * structure.
  *
+ * The attributes string is of the form "key1=value2 key2=value2 ...".
+ * Values may be boolean (true/false or 1/0), integer, float, string,
+ * or an array.
+ *
+ * String values are enclosed in single quotes
+ * ('). Single quotes and backslashes inside the string should be
+ * escaped with a backslash.
+ *
+ * Boolean values may be set to true by only
+ * specifying the key. eg the attribute string "key" is the equivalent
+ * to "key=true".
+ *
+ * Arrays are enclosed in '[]'. eg "rect=[1.2 4.3 2.0 3.0]".
+ *
+ * If no attributes are required, @attributes can be an empty string or NULL.
+ *
+ * See [Tags and Links Description][cairo-Tags-and-Links.description]
+ * for the list of tags and attributes.
+ *
+ * Invalid nesting of tags or invalid attributes will cause @cr to
+ * shutdown with a status of %CAIRO_STATUS_TAG_ERROR.
+ *
+ * See cairo_tag_end().
+ *
  * Since: 1.16
  **/
 void
@@ -2698,6 +2955,9 @@ cairo_tag_begin (cairo_t *cr, const char *tag_name, const char *attributes)
  *
  * Marks the end of the @tag_name structure.
  *
+ * Invalid nesting of tags will cause @cr to shutdown with a status of
+ * %CAIRO_STATUS_TAG_ERROR.
+ *
  * See cairo_tag_begin().
  *
  * Since: 1.16
diff --git a/src/cairo.h b/src/cairo.h
index 97637686e..32fc88b17 100644
--- a/src/cairo.h
+++ b/src/cairo.h
@@ -295,6 +295,7 @@ typedef struct _cairo_user_data_key {
  * @CAIRO_STATUS_PNG_ERROR: error occurred in libpng while reading from or writing to a PNG file (Since 1.16)
  * @CAIRO_STATUS_FREETYPE_ERROR: error occurred in libfreetype (Since 1.16)
  * @CAIRO_STATUS_WIN32_GDI_ERROR: error occurred in the Windows Graphics Device Interface (Since 1.16)
+ * @CAIRO_STATUS_TAG_ERROR: invalid tag name, attributes, or nesting (Since 1.16)
  * @CAIRO_STATUS_LAST_STATUS: this is a special value indicating the number of
  *   status values defined in this enumeration.  When using this value, note
  *   that the version of cairo at run-time may have additional status values
@@ -354,6 +355,7 @@ typedef enum _cairo_status {
     CAIRO_STATUS_PNG_ERROR,
     CAIRO_STATUS_FREETYPE_ERROR,
     CAIRO_STATUS_WIN32_GDI_ERROR,
+    CAIRO_STATUS_TAG_ERROR,
 
     CAIRO_STATUS_LAST_STATUS
 } cairo_status_t;
@@ -1026,6 +1028,9 @@ cairo_rectangle_list_destroy (cairo_rectangle_list_t *rectangle_list);
 
 /* Logical structure tagging functions */
 
+#define CAIRO_TAG_DEST "cairo.dest"
+#define CAIRO_TAG_LINK "Link"
+
 cairo_public void
 cairo_tag_begin (cairo_t *cr, const char *tag_name, const char *attributes);
 
diff --git a/src/cairoint.h b/src/cairoint.h
index f1cd0758e..493d46103 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -282,6 +282,12 @@ _cairo_isdigit (int c)
     return (c >= '0' && c <= '9');
 }
 
+static inline int cairo_const
+_cairo_isalpha (int c)
+{
+    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+}
+
 #include "cairo-types-private.h"
 #include "cairo-cache-private.h"
 #include "cairo-reference-count-private.h"