Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
  2. /* cairo - a vector graphics library with display and print output
  3.  *
  4.  * Copyright © 2002 University of Southern California
  5.  * Copyright © 2005 Red Hat, Inc.
  6.  * Copyright © 2009 Chris Wilson
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it either under the terms of the GNU Lesser General Public
  10.  * License version 2.1 as published by the Free Software Foundation
  11.  * (the "LGPL") or, at your option, under the terms of the Mozilla
  12.  * Public License Version 1.1 (the "MPL"). If you do not alter this
  13.  * notice, a recipient may use your version of this file under either
  14.  * the MPL or the LGPL.
  15.  *
  16.  * You should have received a copy of the LGPL along with this library
  17.  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  18.  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  19.  * You should have received a copy of the MPL along with this library
  20.  * in the file COPYING-MPL-1.1
  21.  *
  22.  * The contents of this file are subject to the Mozilla Public License
  23.  * Version 1.1 (the "License"); you may not use this file except in
  24.  * compliance with the License. You may obtain a copy of the License at
  25.  * http://www.mozilla.org/MPL/
  26.  *
  27.  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  28.  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  29.  * the specific language governing rights and limitations.
  30.  *
  31.  * The Original Code is the cairo graphics library.
  32.  *
  33.  * The Initial Developer of the Original Code is University of Southern
  34.  * California.
  35.  *
  36.  * Contributor(s):
  37.  *      Carl D. Worth <cworth@cworth.org>
  38.  *      Kristian Høgsberg <krh@redhat.com>
  39.  *      Chris Wilson <chris@chris-wilson.co.uk>
  40.  */
  41.  
  42. #include "cairoint.h"
  43. #include "cairo-clip-private.h"
  44. #include "cairo-error-private.h"
  45. #include "cairo-freed-pool-private.h"
  46. #include "cairo-gstate-private.h"
  47. #include "cairo-path-fixed-private.h"
  48. #include "cairo-composite-rectangles-private.h"
  49. #include "cairo-region-private.h"
  50.  
  51. #if HAS_FREED_POOL
  52. static freed_pool_t clip_path_pool;
  53. #endif
  54.  
  55. static cairo_clip_path_t *
  56. _cairo_clip_path_create (cairo_clip_t *clip)
  57. {
  58.     cairo_clip_path_t *clip_path;
  59.  
  60.     clip_path = _freed_pool_get (&clip_path_pool);
  61.     if (unlikely (clip_path == NULL)) {
  62.         clip_path = malloc (sizeof (cairo_clip_path_t));
  63.         if (unlikely (clip_path == NULL))
  64.             return NULL;
  65.     }
  66.  
  67.     CAIRO_REFERENCE_COUNT_INIT (&clip_path->ref_count, 1);
  68.  
  69.     clip_path->flags = 0;
  70.     clip_path->region = NULL;
  71.     clip_path->surface = NULL;
  72.  
  73.     clip_path->prev = clip->path;
  74.     clip->path = clip_path;
  75.  
  76.     return clip_path;
  77. }
  78.  
  79. static cairo_clip_path_t *
  80. _cairo_clip_path_reference (cairo_clip_path_t *clip_path)
  81. {
  82.     assert (CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&clip_path->ref_count));
  83.  
  84.     _cairo_reference_count_inc (&clip_path->ref_count);
  85.  
  86.     return clip_path;
  87. }
  88.  
  89. static void
  90. _cairo_clip_path_destroy (cairo_clip_path_t *clip_path)
  91. {
  92.     assert (CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&clip_path->ref_count));
  93.  
  94.     if (! _cairo_reference_count_dec_and_test (&clip_path->ref_count))
  95.         return;
  96.  
  97.     _cairo_path_fixed_fini (&clip_path->path);
  98.     if (clip_path->region != NULL)
  99.         cairo_region_destroy (clip_path->region);
  100.     if (clip_path->surface != NULL)
  101.         cairo_surface_destroy (clip_path->surface);
  102.  
  103.     if (clip_path->prev != NULL)
  104.         _cairo_clip_path_destroy (clip_path->prev);
  105.  
  106.     _freed_pool_put (&clip_path_pool, clip_path);
  107. }
  108.  
  109. void
  110. _cairo_clip_init (cairo_clip_t *clip)
  111. {
  112.     clip->all_clipped = FALSE;
  113.     clip->path = NULL;
  114. }
  115.  
  116. static void
  117. _cairo_clip_set_all_clipped (cairo_clip_t *clip)
  118. {
  119.     clip->all_clipped = TRUE;
  120.     if (clip->path != NULL) {
  121.         _cairo_clip_path_destroy (clip->path);
  122.         clip->path = NULL;
  123.     }
  124. }
  125.  
  126. static cairo_status_t
  127. _cairo_clip_intersect_rectangle (cairo_clip_t *clip,
  128.                                  const cairo_rectangle_int_t *rect)
  129. {
  130.     cairo_clip_path_t *clip_path;
  131.     cairo_status_t status;
  132.  
  133.     if (clip->path != NULL) {
  134.         if (rect->x <= clip->path->extents.x &&
  135.             rect->y <= clip->path->extents.y &&
  136.             rect->x + rect->width >= clip->path->extents.x + clip->path->extents.width &&
  137.             rect->y + rect->height >= clip->path->extents.y + clip->path->extents.height)
  138.         {
  139.             return CAIRO_STATUS_SUCCESS;
  140.         }
  141.     }
  142.  
  143.     clip_path = _cairo_clip_path_create (clip);
  144.     if (unlikely (clip_path == NULL))
  145.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  146.  
  147.     _cairo_path_fixed_init (&clip_path->path);
  148.  
  149.     status = _cairo_path_fixed_move_to (&clip_path->path,
  150.                                         _cairo_fixed_from_int (rect->x),
  151.                                         _cairo_fixed_from_int (rect->y));
  152.     assert (status == CAIRO_STATUS_SUCCESS);
  153.     status = _cairo_path_fixed_rel_line_to (&clip_path->path,
  154.                                             _cairo_fixed_from_int (rect->width),
  155.                                             _cairo_fixed_from_int (0));
  156.     assert (status == CAIRO_STATUS_SUCCESS);
  157.     status = _cairo_path_fixed_rel_line_to (&clip_path->path,
  158.                                             _cairo_fixed_from_int (0),
  159.                                             _cairo_fixed_from_int (rect->height));
  160.     assert (status == CAIRO_STATUS_SUCCESS);
  161.     status = _cairo_path_fixed_rel_line_to (&clip_path->path,
  162.                                             _cairo_fixed_from_int (-rect->width),
  163.                                             _cairo_fixed_from_int (0));
  164.     assert (status == CAIRO_STATUS_SUCCESS);
  165.     status = _cairo_path_fixed_close_path (&clip_path->path);
  166.     assert (status == CAIRO_STATUS_SUCCESS);
  167.  
  168.     clip_path->fill_rule = CAIRO_FILL_RULE_WINDING;
  169.     clip_path->tolerance = 1;
  170.     clip_path->antialias = CAIRO_ANTIALIAS_DEFAULT;
  171.     clip_path->flags |= CAIRO_CLIP_PATH_IS_BOX;
  172.  
  173.     clip_path->extents = *rect;
  174.     if (clip_path->prev != NULL) {
  175.         if (! _cairo_rectangle_intersect (&clip_path->extents,
  176.                                           &clip_path->prev->extents))
  177.         {
  178.             _cairo_clip_set_all_clipped (clip);
  179.         }
  180.     }
  181.  
  182.     /* could preallocate the region if it proves worthwhile */
  183.  
  184.     return CAIRO_STATUS_SUCCESS;
  185. }
  186.  
  187. cairo_clip_t *
  188. _cairo_clip_init_copy (cairo_clip_t *clip, cairo_clip_t *other)
  189. {
  190.     if (other != NULL) {
  191.         clip->all_clipped = other->all_clipped;
  192.         if (other->path == NULL) {
  193.             clip->path = NULL;
  194.             if (! clip->all_clipped)
  195.                 clip = NULL;
  196.         } else {
  197.             clip->path = _cairo_clip_path_reference (other->path);
  198.         }
  199.     } else {
  200.         _cairo_clip_init (clip);
  201.         clip = NULL;
  202.     }
  203.  
  204.     return clip;
  205. }
  206.  
  207. void
  208. _cairo_clip_reset (cairo_clip_t *clip)
  209. {
  210.     clip->all_clipped = FALSE;
  211.     if (clip->path != NULL) {
  212.         _cairo_clip_path_destroy (clip->path);
  213.         clip->path = NULL;
  214.     }
  215. }
  216.  
  217. static cairo_status_t
  218. _cairo_clip_intersect_path (cairo_clip_t       *clip,
  219.                             const cairo_path_fixed_t *path,
  220.                             cairo_fill_rule_t   fill_rule,
  221.                             double              tolerance,
  222.                             cairo_antialias_t   antialias)
  223. {
  224.     cairo_clip_path_t *clip_path;
  225.     cairo_status_t status;
  226.     cairo_rectangle_int_t extents;
  227.     cairo_box_t box;
  228.     cairo_bool_t is_box = FALSE;
  229.  
  230.     if (clip->path != NULL) {
  231.         if (clip->path->fill_rule == fill_rule &&
  232.             (path->is_rectilinear || tolerance == clip->path->tolerance) &&
  233.             antialias == clip->path->antialias &&
  234.             _cairo_path_fixed_equal (&clip->path->path, path))
  235.         {
  236.             return CAIRO_STATUS_SUCCESS;
  237.         }
  238.     }
  239.  
  240.     _cairo_path_fixed_approximate_clip_extents (path, &extents);
  241.     if (extents.width == 0 || extents.height == 0) {
  242.         _cairo_clip_set_all_clipped (clip);
  243.         return CAIRO_STATUS_SUCCESS;
  244.     }
  245.  
  246.     is_box = _cairo_path_fixed_is_box (path, &box);
  247.     if (clip->path != NULL) {
  248.         if (! _cairo_rectangle_intersect (&extents, &clip->path->extents)) {
  249.             _cairo_clip_set_all_clipped (clip);
  250.             return CAIRO_STATUS_SUCCESS;
  251.         }
  252.  
  253.         /* does this clip wholly subsume the others? */
  254.         if (is_box &&
  255.             box.p1.x <= _cairo_fixed_from_int (clip->path->extents.x) &&
  256.             box.p2.x >= _cairo_fixed_from_int (clip->path->extents.x + clip->path->extents.width) &&
  257.             box.p1.y <= _cairo_fixed_from_int (clip->path->extents.y) &&
  258.             box.p2.y >= _cairo_fixed_from_int (clip->path->extents.y + clip->path->extents.height))
  259.         {
  260.             return CAIRO_STATUS_SUCCESS;
  261.         }
  262.     }
  263.  
  264.     clip_path = _cairo_clip_path_create (clip);
  265.     if (unlikely (clip_path == NULL))
  266.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  267.  
  268.     status = _cairo_path_fixed_init_copy (&clip_path->path, path);
  269.     if (unlikely (status)) {
  270.         clip->path = clip->path->prev;
  271.         _cairo_clip_path_destroy (clip_path);
  272.         return status;
  273.     }
  274.  
  275.     clip_path->extents = extents;
  276.     clip_path->fill_rule = fill_rule;
  277.     clip_path->tolerance = tolerance;
  278.     clip_path->antialias = antialias;
  279.     if (is_box)
  280.         clip_path->flags |= CAIRO_CLIP_PATH_IS_BOX;
  281.  
  282.     return CAIRO_STATUS_SUCCESS;
  283. }
  284.  
  285. cairo_bool_t
  286. _cairo_clip_equal (const cairo_clip_t *clip_a,
  287.                    const cairo_clip_t *clip_b)
  288. {
  289.     const cairo_clip_path_t *clip_path_a, *clip_path_b;
  290.  
  291.     clip_path_a = clip_a->path;
  292.     clip_path_b = clip_b->path;
  293.  
  294.     while (clip_path_a && clip_path_b) {
  295.         if (clip_path_a == clip_path_b)
  296.             return TRUE;
  297.  
  298.         if (clip_path_a->fill_rule != clip_path_b->fill_rule)
  299.             return FALSE;
  300.  
  301.         if (clip_path_a->tolerance != clip_path_b->tolerance)
  302.             return FALSE;
  303.  
  304.         if (clip_path_a->antialias != clip_path_b->antialias)
  305.             return FALSE;
  306.  
  307.         if (! _cairo_path_fixed_equal (&clip_path_a->path, &clip_path_b->path))
  308.             return FALSE;
  309.  
  310.         clip_path_a = clip_path_a->prev;
  311.         clip_path_b = clip_path_b->prev;
  312.     }
  313.  
  314.     return clip_path_a == clip_path_b; /* ie both NULL */
  315. }
  316.  
  317. cairo_status_t
  318. _cairo_clip_clip (cairo_clip_t       *clip,
  319.                   const cairo_path_fixed_t *path,
  320.                   cairo_fill_rule_t   fill_rule,
  321.                   double              tolerance,
  322.                   cairo_antialias_t   antialias)
  323. {
  324.     if (clip->all_clipped)
  325.         return CAIRO_STATUS_SUCCESS;
  326.  
  327.     /* catch the empty clip path */
  328.     if (_cairo_path_fixed_fill_is_empty (path)) {
  329.         _cairo_clip_set_all_clipped (clip);
  330.         return CAIRO_STATUS_SUCCESS;
  331.     }
  332.  
  333.     return _cairo_clip_intersect_path (clip,
  334.                                        path, fill_rule, tolerance,
  335.                                        antialias);
  336. }
  337.  
  338. cairo_status_t
  339. _cairo_clip_rectangle (cairo_clip_t       *clip,
  340.                        const cairo_rectangle_int_t *rectangle)
  341. {
  342.     if (clip->all_clipped)
  343.         return CAIRO_STATUS_SUCCESS;
  344.  
  345.     if (rectangle->width == 0 || rectangle->height == 0) {
  346.         _cairo_clip_set_all_clipped (clip);
  347.         return CAIRO_STATUS_SUCCESS;
  348.     }
  349.  
  350.     /* if a smaller clip has already been set, ignore the new path */
  351.     if (clip->path != NULL) {
  352.         if (rectangle->x <= clip->path->extents.x &&
  353.             rectangle->y <= clip->path->extents.y &&
  354.             rectangle->x + rectangle->width  >= clip->path->extents.x + clip->path->extents.width &&
  355.             rectangle->y + rectangle->height >= clip->path->extents.y + clip->path->extents.height)
  356.         {
  357.             return CAIRO_STATUS_SUCCESS;
  358.         }
  359.     }
  360.  
  361.     return _cairo_clip_intersect_rectangle (clip, rectangle);
  362. }
  363.  
  364. static cairo_status_t
  365. _cairo_clip_path_reapply_clip_path_transform (cairo_clip_t      *clip,
  366.                                               cairo_clip_path_t *other_path,
  367.                                               const cairo_matrix_t *matrix)
  368. {
  369.     cairo_status_t status;
  370.     cairo_clip_path_t *clip_path;
  371.     cairo_bool_t is_empty;
  372.  
  373.     if (other_path->prev != NULL) {
  374.         status = _cairo_clip_path_reapply_clip_path_transform (clip,
  375.                                                                other_path->prev,
  376.                                                                matrix);
  377.         if (unlikely (status))
  378.             return status;
  379.     }
  380.  
  381.     clip_path = _cairo_clip_path_create (clip);
  382.     if (unlikely (clip_path == NULL))
  383.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  384.  
  385.     status = _cairo_path_fixed_init_copy (&clip_path->path,
  386.                                           &other_path->path);
  387.     if (unlikely (status)) {
  388.         clip->path = clip->path->prev;
  389.         _cairo_clip_path_destroy (clip_path);
  390.         return status;
  391.     }
  392.  
  393.     _cairo_path_fixed_transform (&clip_path->path, matrix);
  394.     _cairo_path_fixed_approximate_clip_extents (&clip_path->path,
  395.                                                 &clip_path->extents);
  396.     if (clip_path->prev != NULL) {
  397.         is_empty = _cairo_rectangle_intersect (&clip_path->extents,
  398.                                                &clip_path->prev->extents);
  399.     }
  400.  
  401.     clip_path->fill_rule = other_path->fill_rule;
  402.     clip_path->tolerance = other_path->tolerance;
  403.     clip_path->antialias = other_path->antialias;
  404.  
  405.     return CAIRO_STATUS_SUCCESS;
  406. }
  407.  
  408. static cairo_status_t
  409. _cairo_clip_path_reapply_clip_path_translate (cairo_clip_t      *clip,
  410.                                               cairo_clip_path_t *other_path,
  411.                                               int tx, int ty)
  412. {
  413.     cairo_status_t status;
  414.     cairo_clip_path_t *clip_path;
  415.  
  416.     if (other_path->prev != NULL) {
  417.         status = _cairo_clip_path_reapply_clip_path_translate (clip,
  418.                                                                other_path->prev,
  419.                                                                tx, ty);
  420.         if (unlikely (status))
  421.             return status;
  422.     }
  423.  
  424.     clip_path = _cairo_clip_path_create (clip);
  425.     if (unlikely (clip_path == NULL))
  426.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  427.  
  428.     status = _cairo_path_fixed_init_copy (&clip_path->path,
  429.                                           &other_path->path);
  430.     if (unlikely (status)) {
  431.         clip->path = clip->path->prev;
  432.         _cairo_clip_path_destroy (clip_path);
  433.         return status;
  434.     }
  435.  
  436.     _cairo_path_fixed_translate (&clip_path->path,
  437.                                  _cairo_fixed_from_int (tx),
  438.                                  _cairo_fixed_from_int (ty));
  439.  
  440.     clip_path->fill_rule = other_path->fill_rule;
  441.     clip_path->tolerance = other_path->tolerance;
  442.     clip_path->antialias = other_path->antialias;
  443.  
  444.     clip_path->flags = other_path->flags;
  445.     if (other_path->region != NULL) {
  446.         clip_path->region = cairo_region_copy (other_path->region);
  447.         status = clip_path->region->status;
  448.         if (unlikely (status)) {
  449.             clip->path = clip->path->prev;
  450.             _cairo_clip_path_destroy (clip_path);
  451.             return status;
  452.         }
  453.  
  454.         cairo_region_translate (clip_path->region, tx, ty);
  455.     }
  456.     clip_path->surface = cairo_surface_reference (other_path->surface);
  457.  
  458.     clip_path->extents = other_path->extents;
  459.     clip_path->extents.x += tx;
  460.     clip_path->extents.y += ty;
  461.  
  462.     return CAIRO_STATUS_SUCCESS;
  463. }
  464.  
  465. cairo_status_t
  466. _cairo_clip_init_copy_transformed (cairo_clip_t    *clip,
  467.                                    cairo_clip_t    *other,
  468.                                    const cairo_matrix_t *matrix)
  469. {
  470.     cairo_status_t status = CAIRO_STATUS_SUCCESS;
  471.     int tx, ty;
  472.  
  473.     if (other == NULL) {
  474.         _cairo_clip_init (clip);
  475.         return CAIRO_STATUS_SUCCESS;
  476.     }
  477.  
  478.     if (other->all_clipped) {
  479.         _cairo_clip_init (clip);
  480.         clip->all_clipped = TRUE;
  481.         return CAIRO_STATUS_SUCCESS;
  482.     }
  483.  
  484.     if (_cairo_matrix_is_identity (matrix)) {
  485.         _cairo_clip_init_copy (clip, other);
  486.         return CAIRO_STATUS_SUCCESS;
  487.     }
  488.  
  489.     if (other->path != NULL) {
  490.         _cairo_clip_init (clip);
  491.  
  492.         /* if we only need to translate, so we can reuse the caches... */
  493.         /* XXX we still loose the benefit of constructs when the copy is
  494.          * deleted though. Indirect clip_paths?
  495.          */
  496.         if (_cairo_matrix_is_integer_translation (matrix, &tx, &ty)) {
  497.             status = _cairo_clip_path_reapply_clip_path_translate (clip,
  498.                                                                    other->path,
  499.                                                                    tx, ty);
  500.         } else {
  501.             status = _cairo_clip_path_reapply_clip_path_transform (clip,
  502.                                                                    other->path,
  503.                                                                    matrix);
  504.             if (clip->path->extents.width == 0 &&
  505.                 clip->path->extents.height == 0)
  506.             {
  507.                 _cairo_clip_set_all_clipped (clip);
  508.             }
  509.         }
  510.     }
  511.  
  512.     return status;
  513. }
  514.  
  515. static cairo_status_t
  516. _cairo_clip_apply_clip_path (cairo_clip_t *clip,
  517.                              const cairo_clip_path_t *path)
  518. {
  519.     cairo_status_t status;
  520.  
  521.     if (path->prev != NULL)
  522.         status = _cairo_clip_apply_clip_path (clip, path->prev);
  523.  
  524.     return _cairo_clip_intersect_path (clip,
  525.                                        &path->path,
  526.                                        path->fill_rule,
  527.                                        path->tolerance,
  528.                                        path->antialias);
  529. }
  530.  
  531. cairo_status_t
  532. _cairo_clip_apply_clip (cairo_clip_t *clip,
  533.                         const cairo_clip_t *other)
  534. {
  535.     cairo_status_t status;
  536.  
  537.     if (clip->all_clipped)
  538.         return CAIRO_STATUS_SUCCESS;
  539.  
  540.     if (other->all_clipped) {
  541.         _cairo_clip_set_all_clipped (clip);
  542.         return CAIRO_STATUS_SUCCESS;
  543.     }
  544.  
  545.     status = CAIRO_STATUS_SUCCESS;
  546.     if (other->path != NULL)
  547.         status = _cairo_clip_apply_clip_path (clip, other->path);
  548.  
  549.     return status;
  550. }
  551.  
  552. static inline cairo_bool_t
  553. _clip_paths_are_rectilinear (cairo_clip_path_t *clip_path)
  554. {
  555.     while (clip_path != NULL) {
  556.         if (! clip_path->path.is_rectilinear)
  557.             return FALSE;
  558.  
  559.         clip_path = clip_path->prev;
  560.     }
  561.  
  562.     return TRUE;
  563. }
  564.  
  565. static cairo_int_status_t
  566. _cairo_clip_path_to_region_geometric (cairo_clip_path_t *clip_path)
  567. {
  568.     cairo_traps_t traps;
  569.     cairo_box_t stack_boxes[CAIRO_STACK_ARRAY_LENGTH (cairo_box_t)];
  570.     cairo_box_t *boxes = stack_boxes;
  571.     cairo_status_t status;
  572.     int n;
  573.  
  574.     /* If we have nothing to intersect with this path, then it cannot
  575.      * magically be reduced into a region.
  576.      */
  577.     if (clip_path->prev == NULL)
  578.         goto UNSUPPORTED;
  579.  
  580.     /* Start simple... Intersect some boxes with an arbitrary path. */
  581.     if (! clip_path->path.is_rectilinear)
  582.         goto UNSUPPORTED;
  583.     if (clip_path->prev->prev != NULL)
  584.         goto UNSUPPORTED;
  585.  
  586.     _cairo_traps_init (&traps);
  587.     _cairo_box_from_rectangle (&boxes[0], &clip_path->extents);
  588.     _cairo_traps_limit (&traps, boxes, 1);
  589.  
  590.     status = _cairo_path_fixed_fill_rectilinear_to_traps (&clip_path->path,
  591.                                                           clip_path->fill_rule,
  592.                                                           &traps);
  593.     if (unlikely (_cairo_status_is_error (status)))
  594.         return status;
  595.     if (status == CAIRO_INT_STATUS_UNSUPPORTED)
  596.         goto UNSUPPORTED;
  597.  
  598.     if (traps.num_traps > ARRAY_LENGTH (stack_boxes)) {
  599.         boxes = _cairo_malloc_ab (traps.num_traps, sizeof (cairo_box_t));
  600.         if (unlikely (boxes == NULL))
  601.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  602.     }
  603.  
  604.     for (n = 0; n < traps.num_traps; n++) {
  605.         boxes[n].p1.x = traps.traps[n].left.p1.x;
  606.         boxes[n].p1.y = traps.traps[n].top;
  607.         boxes[n].p2.x = traps.traps[n].right.p1.x;
  608.         boxes[n].p2.y = traps.traps[n].bottom;
  609.     }
  610.  
  611.     _cairo_traps_clear (&traps);
  612.     _cairo_traps_limit (&traps, boxes, n);
  613.     status = _cairo_path_fixed_fill_to_traps (&clip_path->prev->path,
  614.                                               clip_path->prev->fill_rule,
  615.                                               clip_path->prev->tolerance,
  616.                                               &traps);
  617.     if (boxes != stack_boxes)
  618.         free (boxes);
  619.  
  620.     if (unlikely (status))
  621.         return status;
  622.  
  623.     status = _cairo_traps_extract_region (&traps, &clip_path->region);
  624.     _cairo_traps_fini (&traps);
  625.  
  626.     if (status == CAIRO_INT_STATUS_UNSUPPORTED)
  627.         goto UNSUPPORTED;
  628.     if (unlikely (status))
  629.         return status;
  630.  
  631.     clip_path->flags |= CAIRO_CLIP_PATH_HAS_REGION;
  632.     return CAIRO_STATUS_SUCCESS;
  633.  
  634. UNSUPPORTED:
  635.     clip_path->flags |= CAIRO_CLIP_PATH_REGION_IS_UNSUPPORTED;
  636.     return CAIRO_INT_STATUS_UNSUPPORTED;
  637. }
  638.  
  639. static cairo_int_status_t
  640. _cairo_clip_path_to_region (cairo_clip_path_t *clip_path)
  641. {
  642.     cairo_int_status_t status;
  643.     cairo_region_t *prev = NULL;
  644.  
  645.     if (clip_path->flags &
  646.         (CAIRO_CLIP_PATH_HAS_REGION |
  647.          CAIRO_CLIP_PATH_REGION_IS_UNSUPPORTED))
  648.     {
  649.         return clip_path->flags & CAIRO_CLIP_PATH_REGION_IS_UNSUPPORTED ?
  650.             CAIRO_INT_STATUS_UNSUPPORTED :
  651.             CAIRO_STATUS_SUCCESS;
  652.     }
  653.  
  654.     if (! clip_path->path.maybe_fill_region)
  655.         return _cairo_clip_path_to_region_geometric (clip_path);
  656.  
  657.     /* first retrieve the region for our antecedents */
  658.     if (clip_path->prev != NULL) {
  659.         status = _cairo_clip_path_to_region (clip_path->prev);
  660.         if (status) {
  661.             if (status == CAIRO_INT_STATUS_UNSUPPORTED)
  662.                 return _cairo_clip_path_to_region_geometric (clip_path);
  663.  
  664.             return status;
  665.         }
  666.  
  667.         prev = clip_path->prev->region;
  668.     }
  669.  
  670.     /* now extract the region for ourselves */
  671.     clip_path->region =
  672.         _cairo_path_fixed_fill_rectilinear_to_region (&clip_path->path,
  673.                                                       clip_path->fill_rule,
  674.                                                       &clip_path->extents);
  675.     assert (clip_path->region != NULL);
  676.  
  677.     status = clip_path->region->status;
  678.     if (unlikely (status))
  679.         return status;
  680.  
  681.     if (prev != NULL) {
  682.         status = cairo_region_intersect (clip_path->region, prev);
  683.         if (unlikely (status))
  684.             return status;
  685.     }
  686.  
  687.     clip_path->flags |= CAIRO_CLIP_PATH_HAS_REGION;
  688.     return CAIRO_STATUS_SUCCESS;
  689. }
  690.  
  691. static inline int
  692. pot (int v)
  693. {
  694.     v--;
  695.     v |= v >> 1;
  696.     v |= v >> 2;
  697.     v |= v >> 4;
  698.     v |= v >> 8;
  699.     v |= v >> 16;
  700.     v++;
  701.     return v;
  702. }
  703.  
  704. /* XXX there is likely a faster method! ;-) */
  705. static cairo_status_t
  706. _region_clip_to_boxes (const cairo_region_t *region,
  707.                        cairo_box_t **boxes,
  708.                        int *num_boxes,
  709.                        int *size_boxes)
  710. {
  711.     cairo_traps_t traps;
  712.     cairo_status_t status;
  713.     int n, num_rects;
  714.  
  715.     _cairo_traps_init (&traps);
  716.     _cairo_traps_limit (&traps, *boxes, *num_boxes);
  717.     traps.is_rectilinear = TRUE;
  718.     traps.is_rectangular = TRUE;
  719.  
  720.     num_rects = cairo_region_num_rectangles (region);
  721.     for (n = 0; n < num_rects; n++) {
  722.         cairo_rectangle_int_t rect;
  723.         cairo_point_t p1, p2;
  724.  
  725.         cairo_region_get_rectangle (region, n, &rect);
  726.  
  727.         p1.x = _cairo_fixed_from_int (rect.x);
  728.         p1.y = _cairo_fixed_from_int (rect.y);
  729.         p2.x = _cairo_fixed_from_int (rect.x + rect.width);
  730.         p2.y = _cairo_fixed_from_int (rect.y + rect.height);
  731.  
  732.         status = _cairo_traps_tessellate_rectangle (&traps, &p1, &p2);
  733.         if (unlikely (status))
  734.             goto CLEANUP;
  735.     }
  736.  
  737.     status = _cairo_bentley_ottmann_tessellate_rectangular_traps (&traps, CAIRO_FILL_RULE_WINDING);
  738.     if (unlikely (status))
  739.         goto CLEANUP;
  740.  
  741.     n = *size_boxes;
  742.     if (n < 0)
  743.         n = -n;
  744.  
  745.     if (traps.num_traps > n) {
  746.         cairo_box_t *new_boxes;
  747.  
  748.         new_boxes = _cairo_malloc_ab (traps.num_traps, sizeof (cairo_box_t));
  749.         if (unlikely (new_boxes == NULL)) {
  750.             status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
  751.             goto CLEANUP;
  752.         }
  753.  
  754.         if (*size_boxes > 0)
  755.             free (*boxes);
  756.  
  757.         *boxes = new_boxes;
  758.         *size_boxes = traps.num_traps;
  759.     }
  760.  
  761.     for (n = 0; n < traps.num_traps; n++) {
  762.         (*boxes)[n].p1.x = traps.traps[n].left.p1.x;
  763.         (*boxes)[n].p1.y = traps.traps[n].top;
  764.         (*boxes)[n].p2.x = traps.traps[n].right.p1.x;
  765.         (*boxes)[n].p2.y = traps.traps[n].bottom;
  766.     }
  767.     *num_boxes = n;
  768.  
  769.   CLEANUP:
  770.     _cairo_traps_fini (&traps);
  771.  
  772.     return status;
  773. }
  774.  
  775. static cairo_status_t
  776. _rectilinear_clip_to_boxes (const cairo_path_fixed_t *path,
  777.                             cairo_fill_rule_t fill_rule,
  778.                             cairo_box_t **boxes,
  779.                             int *num_boxes,
  780.                             int *size_boxes)
  781. {
  782.     cairo_polygon_t polygon;
  783.     cairo_traps_t traps;
  784.     cairo_status_t status;
  785.  
  786.     _cairo_traps_init (&traps);
  787.     _cairo_traps_limit (&traps, *boxes, *num_boxes);
  788.  
  789.     _cairo_polygon_init (&polygon);
  790.     _cairo_polygon_limit (&polygon, *boxes, *num_boxes);
  791.  
  792.     status = _cairo_path_fixed_fill_rectilinear_to_traps (path,
  793.                                                           fill_rule,
  794.                                                           &traps);
  795.     if (unlikely (_cairo_status_is_error (status)))
  796.         goto CLEANUP;
  797.     if (status == CAIRO_STATUS_SUCCESS)
  798.         goto BOXES;
  799.  
  800.     /* tolerance will be ignored as the path is rectilinear */
  801.     status = _cairo_path_fixed_fill_to_polygon (path, 0., &polygon);
  802.     if (unlikely (status))
  803.         goto CLEANUP;
  804.  
  805.     if (polygon.num_edges == 0) {
  806.         *num_boxes = 0;
  807.     } else {
  808.         status = _cairo_bentley_ottmann_tessellate_rectilinear_polygon (&traps,
  809.                                                                         &polygon,
  810.                                                                         fill_rule);
  811.         if (likely (status == CAIRO_STATUS_SUCCESS)) {
  812.             int i;
  813.  
  814.           BOXES:
  815.             i = *size_boxes;
  816.             if (i < 0)
  817.                 i = -i;
  818.  
  819.             if (traps.num_traps > i) {
  820.                 cairo_box_t *new_boxes;
  821.                 int new_size;
  822.  
  823.                 new_size = pot (traps.num_traps);
  824.                 new_boxes = _cairo_malloc_ab (new_size, sizeof (cairo_box_t));
  825.                 if (unlikely (new_boxes == NULL)) {
  826.                     status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
  827.                     goto CLEANUP;
  828.                 }
  829.  
  830.                 if (*size_boxes > 0)
  831.                     free (*boxes);
  832.  
  833.                 *boxes = new_boxes;
  834.                 *size_boxes = new_size;
  835.             }
  836.  
  837.             for (i = 0; i < traps.num_traps; i++) {
  838.                 (*boxes)[i].p1.x = traps.traps[i].left.p1.x;
  839.                 (*boxes)[i].p1.y = traps.traps[i].top;
  840.                 (*boxes)[i].p2.x = traps.traps[i].right.p1.x;
  841.                 (*boxes)[i].p2.y = traps.traps[i].bottom;
  842.             }
  843.             *num_boxes = i;
  844.         }
  845.     }
  846.  
  847.   CLEANUP:
  848.     _cairo_polygon_fini (&polygon);
  849.     _cairo_traps_fini (&traps);
  850.  
  851.     return status;
  852. }
  853.  
  854. static cairo_int_status_t
  855. _cairo_clip_path_to_boxes (cairo_clip_path_t *clip_path,
  856.                            cairo_box_t **boxes,
  857.                            int *count)
  858. {
  859.     int size = -*count;
  860.     int num_boxes = 0;
  861.     cairo_status_t status;
  862.  
  863.     if (clip_path->region != NULL) {
  864.         int num_rects, n;
  865.  
  866.         num_rects = cairo_region_num_rectangles (clip_path->region);
  867.         if (num_rects > -size) {
  868.             cairo_box_t *new_boxes;
  869.  
  870.             new_boxes = _cairo_malloc_ab (num_rects, sizeof (cairo_box_t));
  871.             if (unlikely (new_boxes == NULL))
  872.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  873.  
  874.             *boxes = new_boxes;
  875.         }
  876.  
  877.         for (n = 0; n < num_rects; n++) {
  878.             cairo_rectangle_int_t rect;
  879.  
  880.             cairo_region_get_rectangle (clip_path->region, n, &rect);
  881.             (*boxes)[n].p1.x = _cairo_fixed_from_int (rect.x);
  882.             (*boxes)[n].p1.y = _cairo_fixed_from_int (rect.y);
  883.             (*boxes)[n].p2.x = _cairo_fixed_from_int (rect.x + rect.width);
  884.             (*boxes)[n].p2.y = _cairo_fixed_from_int (rect.y + rect.height);
  885.         }
  886.  
  887.         *count = num_rects;
  888.         return CAIRO_STATUS_SUCCESS;
  889.     }
  890.  
  891.     /* keep it simple at first */
  892.     if (! _clip_paths_are_rectilinear (clip_path))
  893.         return CAIRO_INT_STATUS_UNSUPPORTED;
  894.  
  895.     assert (-size >= 1);
  896.     if (_cairo_path_fixed_is_box (&clip_path->path, *boxes)) {
  897.         num_boxes = 1;
  898.     } else {
  899.         status = _rectilinear_clip_to_boxes (&clip_path->path,
  900.                                              clip_path->fill_rule,
  901.                                              boxes, &num_boxes, &size);
  902.         if (unlikely (status))
  903.             return status;
  904.     }
  905.  
  906.     while (num_boxes > 0 && (clip_path = clip_path->prev) != NULL) {
  907.         cairo_box_t box;
  908.  
  909.         if (clip_path->region != NULL) {
  910.             status = _region_clip_to_boxes (clip_path->region,
  911.                                             boxes, &num_boxes, &size);
  912.             if (unlikely (status))
  913.                 return status;
  914.  
  915.             break;
  916.         } else if (_cairo_path_fixed_is_box (&clip_path->path, &box)) {
  917.             int i, j;
  918.  
  919.             for (i = j = 0; i < num_boxes; i++) {
  920.                 if (j != i)
  921.                     (*boxes)[j] = (*boxes)[i];
  922.  
  923.                 if (box.p1.x > (*boxes)[j].p1.x)
  924.                     (*boxes)[j].p1.x = box.p1.x;
  925.                 if (box.p2.x < (*boxes)[j].p2.x)
  926.                     (*boxes)[j].p2.x = box.p2.x;
  927.  
  928.                 if (box.p1.y > (*boxes)[j].p1.y)
  929.                     (*boxes)[j].p1.y = box.p1.y;
  930.                 if (box.p2.y < (*boxes)[j].p2.y)
  931.                     (*boxes)[j].p2.y = box.p2.y;
  932.  
  933.                 j += (*boxes)[j].p2.x > (*boxes)[j].p1.x &&
  934.                      (*boxes)[j].p2.y > (*boxes)[j].p1.y;
  935.             }
  936.  
  937.             num_boxes = j;
  938.         } else {
  939.             status = _rectilinear_clip_to_boxes (&clip_path->path,
  940.                                                  clip_path->fill_rule,
  941.                                                  boxes, &num_boxes, &size);
  942.             if (unlikely (status))
  943.                 return status;
  944.         }
  945.     }
  946.  
  947.     *count = num_boxes;
  948.     return CAIRO_STATUS_SUCCESS;
  949. }
  950.  
  951. static cairo_surface_t *
  952. _cairo_clip_path_get_surface (cairo_clip_path_t *clip_path,
  953.                               cairo_surface_t *target,
  954.                               int *tx, int *ty)
  955. {
  956.     const cairo_rectangle_int_t *clip_extents = &clip_path->extents;
  957.     cairo_bool_t need_translate;
  958.     cairo_surface_t *surface;
  959.     cairo_clip_path_t *prev;
  960.     cairo_status_t status;
  961.  
  962.     while (clip_path->prev != NULL &&
  963.            clip_path->flags & CAIRO_CLIP_PATH_IS_BOX &&
  964.            clip_path->path.maybe_fill_region)
  965.     {
  966.         clip_path = clip_path->prev;
  967.     }
  968.  
  969.     clip_extents = &clip_path->extents;
  970.     if (clip_path->surface != NULL &&
  971.         clip_path->surface->backend == target->backend)
  972.     {
  973.         *tx = clip_extents->x;
  974.         *ty = clip_extents->y;
  975.         return clip_path->surface;
  976.     }
  977.  
  978.     surface = _cairo_surface_create_similar_scratch (target,
  979.                                                      CAIRO_CONTENT_ALPHA,
  980.                                                      clip_extents->width,
  981.                                                      clip_extents->height);
  982.     if (surface == NULL) {
  983.         surface = cairo_image_surface_create (CAIRO_FORMAT_A8,
  984.                                               clip_extents->width,
  985.                                               clip_extents->height);
  986.     }
  987.     if (unlikely (surface->status))
  988.         return surface;
  989.  
  990.     need_translate = clip_extents->x | clip_extents->y;
  991.     if (clip_path->flags & CAIRO_CLIP_PATH_IS_BOX &&
  992.         clip_path->path.maybe_fill_region)
  993.     {
  994.         status = _cairo_surface_paint (surface,
  995.                                        CAIRO_OPERATOR_SOURCE,
  996.                                        &_cairo_pattern_white.base,
  997.                                        NULL);
  998.         if (unlikely (status))
  999.             goto BAIL;
  1000.     }
  1001.     else
  1002.     {
  1003.         status = _cairo_surface_paint (surface,
  1004.                                        CAIRO_OPERATOR_CLEAR,
  1005.                                        &_cairo_pattern_clear.base,
  1006.                                        NULL);
  1007.         if (unlikely (status))
  1008.             goto BAIL;
  1009.  
  1010.         if (need_translate) {
  1011.             _cairo_path_fixed_translate (&clip_path->path,
  1012.                                          _cairo_fixed_from_int (-clip_extents->x),
  1013.                                          _cairo_fixed_from_int (-clip_extents->y));
  1014.         }
  1015.         status = _cairo_surface_fill (surface,
  1016.                                       CAIRO_OPERATOR_ADD,
  1017.                                       &_cairo_pattern_white.base,
  1018.                                       &clip_path->path,
  1019.                                       clip_path->fill_rule,
  1020.                                       clip_path->tolerance,
  1021.                                       clip_path->antialias,
  1022.                                       NULL);
  1023.         if (need_translate) {
  1024.             _cairo_path_fixed_translate (&clip_path->path,
  1025.                                          _cairo_fixed_from_int (clip_extents->x),
  1026.                                          _cairo_fixed_from_int (clip_extents->y));
  1027.         }
  1028.  
  1029.         if (unlikely (status))
  1030.             goto BAIL;
  1031.     }
  1032.  
  1033.     prev = clip_path->prev;
  1034.     while (prev != NULL) {
  1035.         if (prev->flags & CAIRO_CLIP_PATH_IS_BOX &&
  1036.             prev->path.maybe_fill_region)
  1037.         {
  1038.             /* a simple box only affects the extents */
  1039.         }
  1040.         else if (prev->path.is_rectilinear ||
  1041.                 prev->surface == NULL ||
  1042.                 prev->surface->backend != target->backend)
  1043.         {
  1044.             if (need_translate) {
  1045.                 _cairo_path_fixed_translate (&prev->path,
  1046.                                              _cairo_fixed_from_int (-clip_extents->x),
  1047.                                              _cairo_fixed_from_int (-clip_extents->y));
  1048.             }
  1049.             status = _cairo_surface_fill (surface,
  1050.                                           CAIRO_OPERATOR_IN,
  1051.                                           &_cairo_pattern_white.base,
  1052.                                           &prev->path,
  1053.                                           prev->fill_rule,
  1054.                                           prev->tolerance,
  1055.                                           prev->antialias,
  1056.                                           NULL);
  1057.             if (need_translate) {
  1058.                 _cairo_path_fixed_translate (&prev->path,
  1059.                                              _cairo_fixed_from_int (clip_extents->x),
  1060.                                              _cairo_fixed_from_int (clip_extents->y));
  1061.             }
  1062.  
  1063.             if (unlikely (status))
  1064.                 goto BAIL;
  1065.         }
  1066.         else
  1067.         {
  1068.             cairo_surface_pattern_t pattern;
  1069.             cairo_surface_t *prev_surface;
  1070.             int prev_tx, prev_ty;
  1071.  
  1072.             prev_surface = _cairo_clip_path_get_surface (prev, target, &prev_tx, &prev_ty);
  1073.             status = prev_surface->status;
  1074.             if (unlikely (status))
  1075.                 goto BAIL;
  1076.  
  1077.             _cairo_pattern_init_for_surface (&pattern, prev_surface);
  1078.             pattern.base.filter = CAIRO_FILTER_NEAREST;
  1079.             cairo_matrix_init_translate (&pattern.base.matrix,
  1080.                                          clip_extents->x - prev_tx,
  1081.                                          clip_extents->y - prev_ty);
  1082.             status = _cairo_surface_paint (surface,
  1083.                                            CAIRO_OPERATOR_IN,
  1084.                                            &pattern.base,
  1085.                                            NULL);
  1086.             _cairo_pattern_fini (&pattern.base);
  1087.  
  1088.             if (unlikely (status))
  1089.                 goto BAIL;
  1090.  
  1091.             break;
  1092.         }
  1093.  
  1094.         prev = prev->prev;
  1095.     }
  1096.  
  1097.     *tx = clip_extents->x;
  1098.     *ty = clip_extents->y;
  1099.     cairo_surface_destroy (clip_path->surface);
  1100.     return clip_path->surface = surface;
  1101.  
  1102.   BAIL:
  1103.     cairo_surface_destroy (surface);
  1104.     return _cairo_surface_create_in_error (status);
  1105. }
  1106.  
  1107. cairo_bool_t
  1108. _cairo_clip_contains_rectangle (cairo_clip_t *clip,
  1109.                                 const cairo_rectangle_int_t *rect)
  1110. {
  1111.     cairo_clip_path_t *clip_path;
  1112.  
  1113.     if (clip == NULL)
  1114.         return FALSE;
  1115.  
  1116.     clip_path = clip->path;
  1117.     if (clip_path->extents.x > rect->x ||
  1118.         clip_path->extents.y > rect->y ||
  1119.         clip_path->extents.x + clip_path->extents.width  < rect->x + rect->width ||
  1120.         clip_path->extents.y + clip_path->extents.height < rect->y + rect->height)
  1121.     {
  1122.         return FALSE;
  1123.     }
  1124.  
  1125.     do {
  1126.         cairo_box_t box;
  1127.  
  1128.         if ((clip_path->flags & CAIRO_CLIP_PATH_IS_BOX) == 0)
  1129.             return FALSE;
  1130.  
  1131.         if (! _cairo_path_fixed_is_box (&clip_path->path, &box))
  1132.             return FALSE;
  1133.  
  1134.         if (box.p1.x > _cairo_fixed_from_int (rect->x) ||
  1135.             box.p1.y > _cairo_fixed_from_int (rect->y) ||
  1136.             box.p2.x < _cairo_fixed_from_int (rect->x + rect->width) ||
  1137.             box.p2.y < _cairo_fixed_from_int (rect->y + rect->height))
  1138.         {
  1139.             return FALSE;
  1140.         }
  1141.     } while ((clip_path = clip_path->prev) != NULL);
  1142.  
  1143.     return TRUE;
  1144. }
  1145.  
  1146. cairo_bool_t
  1147. _cairo_clip_contains_extents (cairo_clip_t *clip,
  1148.                               const cairo_composite_rectangles_t *extents)
  1149. {
  1150.     const cairo_rectangle_int_t *rect;
  1151.  
  1152.     if (clip == NULL)
  1153.         return FALSE;
  1154.  
  1155.     rect = extents->is_bounded ? &extents->bounded : &extents->unbounded;
  1156.     return _cairo_clip_contains_rectangle (clip, rect);
  1157. }
  1158.  
  1159. void
  1160. _cairo_debug_print_clip (FILE *stream, cairo_clip_t *clip)
  1161. {
  1162.     cairo_clip_path_t *clip_path;
  1163.  
  1164.     if (clip == NULL) {
  1165.         fprintf (stream, "no clip\n");
  1166.         return;
  1167.     }
  1168.  
  1169.     if (clip->all_clipped) {
  1170.         fprintf (stream, "clip: all-clipped\n");
  1171.         return;
  1172.     }
  1173.  
  1174.     if (clip->path == NULL) {
  1175.         fprintf (stream, "clip: empty\n");
  1176.         return;
  1177.     }
  1178.  
  1179.     fprintf (stream, "clip:\n");
  1180.  
  1181.     clip_path = clip->path;
  1182.     do {
  1183.         fprintf (stream, "path: has region? %s, has surface? %s, aa=%d, tolerance=%f, rule=%d: ",
  1184.                  clip_path->region == NULL ? "no" : "yes",
  1185.                  clip_path->surface == NULL ? "no" : "yes",
  1186.                  clip_path->antialias,
  1187.                  clip_path->tolerance,
  1188.                  clip_path->fill_rule);
  1189.         _cairo_debug_print_path (stream, &clip_path->path);
  1190.         fprintf (stream, "\n");
  1191.     } while ((clip_path = clip_path->prev) != NULL);
  1192. }
  1193.  
  1194. cairo_surface_t *
  1195. _cairo_clip_get_surface (cairo_clip_t *clip, cairo_surface_t *target, int *tx, int *ty)
  1196. {
  1197.     /* XXX is_clear -> all_clipped */
  1198.     assert (clip->path != NULL);
  1199.     return _cairo_clip_path_get_surface (clip->path, target, tx, ty);
  1200. }
  1201.  
  1202. cairo_status_t
  1203. _cairo_clip_combine_with_surface (cairo_clip_t *clip,
  1204.                                   cairo_surface_t *dst,
  1205.                                   int dst_x, int dst_y)
  1206. {
  1207.     cairo_clip_path_t *clip_path = clip->path;
  1208.     cairo_bool_t need_translate;
  1209.     cairo_status_t status;
  1210.  
  1211.     assert (clip_path != NULL);
  1212.  
  1213.     need_translate = dst_x | dst_y;
  1214.     do {
  1215.         if (clip_path->surface != NULL &&
  1216.             clip_path->surface->backend == dst->backend)
  1217.         {
  1218.             cairo_surface_pattern_t pattern;
  1219.  
  1220.             _cairo_pattern_init_for_surface (&pattern, clip_path->surface);
  1221.             cairo_matrix_init_translate (&pattern.base.matrix,
  1222.                                          dst_x - clip_path->extents.x,
  1223.                                          dst_y - clip_path->extents.y);
  1224.             pattern.base.filter = CAIRO_FILTER_NEAREST;
  1225.             status = _cairo_surface_paint (dst,
  1226.                                            CAIRO_OPERATOR_IN,
  1227.                                            &pattern.base,
  1228.                                            NULL);
  1229.  
  1230.             _cairo_pattern_fini (&pattern.base);
  1231.  
  1232.             return status;
  1233.         }
  1234.  
  1235.         if (clip_path->flags & CAIRO_CLIP_PATH_IS_BOX &&
  1236.             clip_path->path.maybe_fill_region)
  1237.         {
  1238.             continue;
  1239.         }
  1240.  
  1241.         if (need_translate) {
  1242.             _cairo_path_fixed_translate (&clip_path->path,
  1243.                                          _cairo_fixed_from_int (-dst_x),
  1244.                                          _cairo_fixed_from_int (-dst_y));
  1245.         }
  1246.         status = _cairo_surface_fill (dst,
  1247.                                       CAIRO_OPERATOR_IN,
  1248.                                       &_cairo_pattern_white.base,
  1249.                                       &clip_path->path,
  1250.                                       clip_path->fill_rule,
  1251.                                       clip_path->tolerance,
  1252.                                       clip_path->antialias,
  1253.                                       NULL);
  1254.         if (need_translate) {
  1255.             _cairo_path_fixed_translate (&clip_path->path,
  1256.                                          _cairo_fixed_from_int (dst_x),
  1257.                                          _cairo_fixed_from_int (dst_y));
  1258.         }
  1259.  
  1260.         if (unlikely (status))
  1261.             return status;
  1262.     } while ((clip_path = clip_path->prev) != NULL);
  1263.  
  1264.     return CAIRO_STATUS_SUCCESS;
  1265. }
  1266.  
  1267. static const cairo_rectangle_int_t _cairo_empty_rectangle_int = { 0, 0, 0, 0 };
  1268.  
  1269. const cairo_rectangle_int_t *
  1270. _cairo_clip_get_extents (const cairo_clip_t *clip)
  1271. {
  1272.     if (clip->all_clipped)
  1273.         return &_cairo_empty_rectangle_int;
  1274.  
  1275.     if (clip->path == NULL)
  1276.         return NULL;
  1277.  
  1278.     return &clip->path->extents;
  1279. }
  1280.  
  1281. void
  1282. _cairo_clip_drop_cache (cairo_clip_t  *clip)
  1283. {
  1284.     cairo_clip_path_t *clip_path;
  1285.  
  1286.     if (clip->path == NULL)
  1287.         return;
  1288.  
  1289.     clip_path = clip->path;
  1290.     do {
  1291.         if (clip_path->region != NULL) {
  1292.             cairo_region_destroy (clip_path->region);
  1293.             clip_path->region = NULL;
  1294.         }
  1295.  
  1296.         if (clip_path->surface != NULL) {
  1297.             cairo_surface_destroy (clip_path->surface);
  1298.             clip_path->surface = NULL;
  1299.         }
  1300.  
  1301.         clip_path->flags &= ~CAIRO_CLIP_PATH_HAS_REGION;
  1302.     } while ((clip_path = clip_path->prev) != NULL);
  1303. }
  1304.  
  1305. const cairo_rectangle_list_t _cairo_rectangles_nil =
  1306.   { CAIRO_STATUS_NO_MEMORY, NULL, 0 };
  1307. static const cairo_rectangle_list_t _cairo_rectangles_not_representable =
  1308.   { CAIRO_STATUS_CLIP_NOT_REPRESENTABLE, NULL, 0 };
  1309.  
  1310. static cairo_bool_t
  1311. _cairo_clip_int_rect_to_user (cairo_gstate_t *gstate,
  1312.                               cairo_rectangle_int_t *clip_rect,
  1313.                               cairo_rectangle_t *user_rect)
  1314. {
  1315.     cairo_bool_t is_tight;
  1316.  
  1317.     double x1 = clip_rect->x;
  1318.     double y1 = clip_rect->y;
  1319.     double x2 = clip_rect->x + (int) clip_rect->width;
  1320.     double y2 = clip_rect->y + (int) clip_rect->height;
  1321.  
  1322.     _cairo_gstate_backend_to_user_rectangle (gstate,
  1323.                                              &x1, &y1, &x2, &y2,
  1324.                                              &is_tight);
  1325.  
  1326.     user_rect->x = x1;
  1327.     user_rect->y = y1;
  1328.     user_rect->width  = x2 - x1;
  1329.     user_rect->height = y2 - y1;
  1330.  
  1331.     return is_tight;
  1332. }
  1333.  
  1334. cairo_int_status_t
  1335. _cairo_clip_get_region (cairo_clip_t *clip,
  1336.                         cairo_region_t **region)
  1337. {
  1338.     cairo_int_status_t status;
  1339.  
  1340.     if (clip->all_clipped)
  1341.         goto CLIPPED;
  1342.  
  1343.     assert (clip->path != NULL);
  1344.  
  1345.     status = _cairo_clip_path_to_region (clip->path);
  1346.     if (status)
  1347.         return status;
  1348.  
  1349.     if (cairo_region_is_empty (clip->path->region)) {
  1350.         _cairo_clip_set_all_clipped (clip);
  1351.         goto CLIPPED;
  1352.     }
  1353.  
  1354.     if (region)
  1355.         *region = clip->path->region;
  1356.     return CAIRO_STATUS_SUCCESS;
  1357.  
  1358.   CLIPPED:
  1359.     if (region)
  1360.         *region = NULL;
  1361.     return CAIRO_INT_STATUS_NOTHING_TO_DO;
  1362. }
  1363.  
  1364. cairo_int_status_t
  1365. _cairo_clip_get_boxes (cairo_clip_t *clip,
  1366.                        cairo_box_t **boxes,
  1367.                        int *count)
  1368. {
  1369.     cairo_int_status_t status;
  1370.  
  1371.     if (clip->all_clipped)
  1372.         return CAIRO_INT_STATUS_NOTHING_TO_DO;
  1373.  
  1374.     assert (clip->path != NULL);
  1375.  
  1376.     status = _cairo_clip_path_to_boxes (clip->path, boxes, count);
  1377.     if (status)
  1378.         return status;
  1379.  
  1380.     if (*count == 0) {
  1381.         _cairo_clip_set_all_clipped (clip);
  1382.         return CAIRO_INT_STATUS_NOTHING_TO_DO;
  1383.     }
  1384.  
  1385.     return CAIRO_STATUS_SUCCESS;
  1386. }
  1387.  
  1388. static cairo_bool_t
  1389. box_is_aligned (const cairo_box_t *box)
  1390. {
  1391.     return
  1392.         _cairo_fixed_is_integer (box->p1.x) &&
  1393.         _cairo_fixed_is_integer (box->p1.y) &&
  1394.         _cairo_fixed_is_integer (box->p2.x) &&
  1395.         _cairo_fixed_is_integer (box->p2.y);
  1396. }
  1397.  
  1398. static void
  1399. intersect_with_boxes (cairo_composite_rectangles_t *extents,
  1400.                       cairo_box_t *boxes,
  1401.                       int num_boxes)
  1402. {
  1403.     cairo_rectangle_int_t rect;
  1404.     cairo_box_t box;
  1405.     cairo_bool_t is_empty;
  1406.  
  1407.     box.p1.x = box.p1.y = INT_MIN;
  1408.     box.p2.x = box.p2.y = INT_MAX;
  1409.     while (num_boxes--) {
  1410.         if (boxes->p1.x < box.p1.x)
  1411.             box.p1.x = boxes->p1.x;
  1412.         if (boxes->p1.y < box.p1.y)
  1413.             box.p1.y = boxes->p1.y;
  1414.  
  1415.         if (boxes->p2.x > box.p2.x)
  1416.             box.p2.x = boxes->p2.x;
  1417.         if (boxes->p2.y > box.p2.y)
  1418.             box.p2.y = boxes->p2.y;
  1419.     }
  1420.  
  1421.     _cairo_box_round_to_rectangle (&box, &rect);
  1422.     is_empty = _cairo_rectangle_intersect (&extents->bounded, &rect);
  1423.     is_empty = _cairo_rectangle_intersect (&extents->unbounded, &rect);
  1424. }
  1425.  
  1426. cairo_status_t
  1427. _cairo_clip_to_boxes (cairo_clip_t **clip,
  1428.                       cairo_composite_rectangles_t *extents,
  1429.                       cairo_box_t **boxes,
  1430.                       int *num_boxes)
  1431. {
  1432.     cairo_status_t status;
  1433.     const cairo_rectangle_int_t *rect;
  1434.  
  1435.     rect = extents->is_bounded ? &extents->bounded : &extents->unbounded;
  1436.  
  1437.     if (*clip == NULL)
  1438.         goto EXTENTS;
  1439.  
  1440.     status = _cairo_clip_rectangle (*clip, rect);
  1441.     if (unlikely (status))
  1442.         return status;
  1443.  
  1444.     status = _cairo_clip_get_boxes (*clip, boxes, num_boxes);
  1445.     switch ((int) status) {
  1446.     case CAIRO_STATUS_SUCCESS:
  1447.         intersect_with_boxes (extents, *boxes, *num_boxes);
  1448.         if (rect->width == 0 || rect->height == 0 ||
  1449.             extents->is_bounded ||
  1450.             (*num_boxes == 1 && box_is_aligned (*boxes)))
  1451.         {
  1452.             *clip = NULL;
  1453.         }
  1454.         goto DONE;
  1455.  
  1456.     case CAIRO_INT_STATUS_UNSUPPORTED:
  1457.         goto EXTENTS;
  1458.  
  1459.     default:
  1460.         return status;
  1461.     }
  1462.  
  1463.   EXTENTS:
  1464.     status = CAIRO_STATUS_SUCCESS;
  1465.     _cairo_box_from_rectangle (&(*boxes)[0], rect);
  1466.     *num_boxes = 1;
  1467.   DONE:
  1468.     return status;
  1469. }
  1470.  
  1471.  
  1472. static cairo_rectangle_list_t *
  1473. _cairo_rectangle_list_create_in_error (cairo_status_t status)
  1474. {
  1475.     cairo_rectangle_list_t *list;
  1476.  
  1477.     if (status == CAIRO_STATUS_NO_MEMORY)
  1478.         return (cairo_rectangle_list_t*) &_cairo_rectangles_nil;
  1479.     if (status == CAIRO_STATUS_CLIP_NOT_REPRESENTABLE)
  1480.         return (cairo_rectangle_list_t*) &_cairo_rectangles_not_representable;
  1481.  
  1482.     list = malloc (sizeof (*list));
  1483.     if (unlikely (list == NULL)) {
  1484.         _cairo_error_throw (status);
  1485.         return (cairo_rectangle_list_t*) &_cairo_rectangles_nil;
  1486.     }
  1487.  
  1488.     list->status = status;
  1489.     list->rectangles = NULL;
  1490.     list->num_rectangles = 0;
  1491.  
  1492.     return list;
  1493. }
  1494.  
  1495. cairo_rectangle_list_t *
  1496. _cairo_clip_copy_rectangle_list (cairo_clip_t *clip, cairo_gstate_t *gstate)
  1497. {
  1498. #define ERROR_LIST(S) _cairo_rectangle_list_create_in_error (_cairo_error (S))
  1499.  
  1500.     cairo_rectangle_list_t *list;
  1501.     cairo_rectangle_t *rectangles = NULL;
  1502.     cairo_region_t *region = NULL;
  1503.     cairo_int_status_t status;
  1504.     int n_rects = 0;
  1505.     int i;
  1506.  
  1507.     if (clip->all_clipped)
  1508.         goto DONE;
  1509.  
  1510.     if (!clip->path)
  1511.         return ERROR_LIST (CAIRO_STATUS_CLIP_NOT_REPRESENTABLE);
  1512.  
  1513.     status = _cairo_clip_get_region (clip, &region);
  1514.     if (status == CAIRO_INT_STATUS_NOTHING_TO_DO) {
  1515.         goto DONE;
  1516.     } else if (status == CAIRO_INT_STATUS_UNSUPPORTED) {
  1517.         return ERROR_LIST (CAIRO_STATUS_CLIP_NOT_REPRESENTABLE);
  1518.     } else if (unlikely (status)) {
  1519.         return ERROR_LIST (status);
  1520.     }
  1521.  
  1522.     n_rects = cairo_region_num_rectangles (region);
  1523.     if (n_rects) {
  1524.         rectangles = _cairo_malloc_ab (n_rects, sizeof (cairo_rectangle_t));
  1525.         if (unlikely (rectangles == NULL)) {
  1526.             return ERROR_LIST (CAIRO_STATUS_NO_MEMORY);
  1527.         }
  1528.  
  1529.         for (i = 0; i < n_rects; ++i) {
  1530.             cairo_rectangle_int_t clip_rect;
  1531.  
  1532.             cairo_region_get_rectangle (region, i, &clip_rect);
  1533.  
  1534.             if (! _cairo_clip_int_rect_to_user (gstate,
  1535.                                                 &clip_rect,
  1536.                                                 &rectangles[i]))
  1537.             {
  1538.                 free (rectangles);
  1539.                 return ERROR_LIST (CAIRO_STATUS_CLIP_NOT_REPRESENTABLE);
  1540.             }
  1541.         }
  1542.     }
  1543.  
  1544.  DONE:
  1545.     list = malloc (sizeof (cairo_rectangle_list_t));
  1546.     if (unlikely (list == NULL)) {
  1547.         free (rectangles);
  1548.         return ERROR_LIST (CAIRO_STATUS_NO_MEMORY);
  1549.     }
  1550.  
  1551.     list->status = CAIRO_STATUS_SUCCESS;
  1552.     list->rectangles = rectangles;
  1553.     list->num_rectangles = n_rects;
  1554.     return list;
  1555.  
  1556. #undef ERROR_LIST
  1557. }
  1558.  
  1559. /**
  1560.  * cairo_rectangle_list_destroy:
  1561.  * @rectangle_list: a rectangle list, as obtained from cairo_copy_clip_rectangles()
  1562.  *
  1563.  * Unconditionally frees @rectangle_list and all associated
  1564.  * references. After this call, the @rectangle_list pointer must not
  1565.  * be dereferenced.
  1566.  *
  1567.  * Since: 1.4
  1568.  **/
  1569. void
  1570. cairo_rectangle_list_destroy (cairo_rectangle_list_t *rectangle_list)
  1571. {
  1572.     if (rectangle_list == NULL || rectangle_list == &_cairo_rectangles_nil ||
  1573.         rectangle_list == &_cairo_rectangles_not_representable)
  1574.         return;
  1575.  
  1576.     free (rectangle_list->rectangles);
  1577.     free (rectangle_list);
  1578. }
  1579.  
  1580. void
  1581. _cairo_clip_reset_static_data (void)
  1582. {
  1583.     _freed_pool_reset (&clip_path_pool);
  1584. }
  1585.