src/libnrtype/Layout-TNG-OutIter.cpp

   1 /*
   2  * Inkscape::Text::Layout - text layout engine output functions using iterators
   3  *
   4  * Authors:
   5  *   Richard Hughes <cyreve@users.sf.net>
   6  *
   7  * Copyright (C) 2005 Richard Hughes
   8  *
   9  * Released under GNU GPL, read the file 'COPYING' for more information
  10  */
  11 #include "Layout-TNG.h"
  12 #include "livarot/Path.h"
  13 #include "font-instance.h"
  14 #include "svg/svg-length.h"
  15 #include "libnr/nr-matrix-translate-ops.h"
  16 #include "libnr/nr-translate-rotate-ops.h"
  17 #include "style.h"
  18
  19 namespace Inkscape {
  20 namespace Text {
  21
  22 Layout::iterator Layout::_cursorXOnLineToIterator(unsigned line_index, double local_x) const
  23 {
  24     unsigned char_index = _lineToCharacter(line_index);
  25     int best_char_index = -1;
  26     double best_x_difference = DBL_MAX;
  27
  28     if (char_index == _characters.size()) return end();
  29     for ( ; char_index < _characters.size() ; char_index++) {
  30         if (_characters[char_index].chunk(this).in_line != line_index) break;
  31         if (_characters[char_index].char_attributes.is_mandatory_break) break;
  32         if (!_characters[char_index].char_attributes.is_cursor_position) continue;
  33         double this_x_difference = fabs(_characters[char_index].x + _characters[char_index].span(this).x_start + _characters[char_index].chunk(this).left_x - local_x);
  34         if (this_x_difference < best_x_difference) {
  35             best_char_index = char_index;
  36             best_x_difference = this_x_difference;
  37         }
  38     }
  39     // also try the very end of a para (not lines though because the space wraps)
  40     if (char_index == _characters.size() || _characters[char_index].char_attributes.is_mandatory_break) {
  41         double this_x_difference;
  42         if (char_index == 0) this_x_difference = fabs(_spans.front().x_end + _chunks.front().left_x - local_x);
  43         else this_x_difference = fabs(_characters[char_index - 1].span(this).x_end + _characters[char_index - 1].chunk(this).left_x - local_x);
  44         if (this_x_difference < best_x_difference) {
  45             best_char_index = char_index;
  46             best_x_difference = this_x_difference;
  47         }
  48     }
  49     if (best_char_index == -1) return iterator(this, char_index);
  50     return iterator(this, best_char_index);
  51 }
  52
  53 double Layout::_getChunkWidth(unsigned chunk_index) const
  54 {
  55     double chunk_width = 0.0;
  56     unsigned span_index;
  57     if (chunk_index) {
  58         span_index = _lineToSpan(_chunks[chunk_index].in_line);
  59         for ( ; span_index < _spans.size() && _spans[span_index].in_chunk < chunk_index ; span_index++);
  60     } else
  61         span_index = 0;
  62     for ( ; span_index < _spans.size() && _spans[span_index].in_chunk == chunk_index ; span_index++)
  63         chunk_width = std::max(chunk_width, (double)std::max(_spans[span_index].x_start, _spans[span_index].x_end));
  64     return chunk_width;
  65 }
  66
  67 /* getting the cursor position for a mouse click is not as simple as it might
  68 seem. The two major problems are flows set up in multiple columns and large
  69 dy adjustments such that text does not belong to the line it appears to. In
  70 the worst case it's possible to have two characters on top of each other, in
  71 which case the one we pick is arbitrary.
  72
  73 This is a 3-stage (2 pass) algorithm:
  74 1) search all the spans to see if the point is contained in one, if so take
  75    that. Note that this will collect all clicks from the current UI because
  76    of how the hit detection of nrarena objects works.
  77 2) if that fails, run through all the chunks finding a best guess of the one
  78    the user wanted. This is the one whose y coordinate is nearest, or if
  79    there's a tie, the x.
  80 3) search in that chunk using x-coordinate only to find the position.
  81 */
  82 Layout::iterator Layout::getNearestCursorPositionTo(double x, double y) const
  83 {
  84     if (_lines.empty()) return begin();
  85     double local_x = x;
  86     double local_y = y;
  87
  88     if (_path_fitted) {
  89         Path::cut_position position = const_cast<Path*>(_path_fitted)->PointToCurvilignPosition(NR::Point(x, y));
  90         local_x = const_cast<Path*>(_path_fitted)->PositionToLength(position.piece, position.t);
  91         return _cursorXOnLineToIterator(0, local_x + _chunks.front().left_x);
  92     }
  93
  94     if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
  95         local_x = y;
  96         local_y = x;
  97     }
  98     // stage 1:
  99     for (unsigned span_index = 0 ; span_index < _spans.size() ; span_index++) {
 100         double span_left, span_right;
 101         if (_spans[span_index].x_start < _spans[span_index].x_end) {
 102             span_left = _spans[span_index].x_start;
 103             span_right = _spans[span_index].x_end;
 104         } else {
 105             span_left = _spans[span_index].x_end;
 106             span_right = _spans[span_index].x_start;
 107         }
 108         if (   local_x >= _chunks[_spans[span_index].in_chunk].left_x + span_left
 109             && local_x <= _chunks[_spans[span_index].in_chunk].left_x + span_right
 110             && local_y >= _spans[span_index].line(this).baseline_y + _spans[span_index].baseline_shift - _spans[span_index].line_height.ascent
 111             && local_y <= _spans[span_index].line(this).baseline_y + _spans[span_index].baseline_shift + _spans[span_index].line_height.descent) {
 112             return _cursorXOnLineToIterator(_chunks[_spans[span_index].in_chunk].in_line, local_x);
 113         }
 114     }
 115
 116     // stage 2:
 117     unsigned span_index = 0;
 118     unsigned chunk_index;
 119     int best_chunk_index = -1;
 120     double best_y_range = DBL_MAX;
 121     double best_x_range = DBL_MAX;
 122     for (chunk_index = 0 ; chunk_index < _chunks.size() ; chunk_index++) {
 123         LineHeight line_height = {0.0, 0.0, 0.0};
 124         double chunk_width = 0.0;
 125         for ( ; span_index < _spans.size() && _spans[span_index].in_chunk == chunk_index ; span_index++) {
 126             line_height.max(_spans[span_index].line_height);
 127             chunk_width = std::max(chunk_width, (double)std::max(_spans[span_index].x_start, _spans[span_index].x_end));
 128         }
 129         double this_y_range;
 130         if (local_y < _lines[_chunks[chunk_index].in_line].baseline_y - line_height.ascent)
 131             this_y_range = _lines[_chunks[chunk_index].in_line].baseline_y - line_height.ascent - local_y;
 132         else if (local_y > _lines[_chunks[chunk_index].in_line].baseline_y + line_height.descent)
 133             this_y_range = local_y - (_lines[_chunks[chunk_index].in_line].baseline_y + line_height.descent);
 134         else
 135             this_y_range = 0.0;
 136         if (this_y_range <= best_y_range) {
 137             if (this_y_range < best_y_range) best_x_range = DBL_MAX;
 138             double this_x_range;
 139             if (local_x < _chunks[chunk_index].left_x)
 140                 this_x_range = _chunks[chunk_index].left_x - local_y;
 141             else if (local_x > _chunks[chunk_index].left_x + chunk_width)
 142                 this_x_range = local_x - (_chunks[chunk_index].left_x + chunk_width);
 143             else
 144                 this_x_range = 0.0;
 145             if (this_x_range < best_x_range) {
 146                 best_y_range = this_y_range;
 147                 best_x_range = this_x_range;
 148                 best_chunk_index = chunk_index;
 149             }
 150         }
 151     }
 152
 153     // stage 3:
 154     if (best_chunk_index == -1) return begin();    // never happens
 155     return _cursorXOnLineToIterator(_chunks[best_chunk_index].in_line, local_x);
 156 }
 157
 158 Layout::iterator Layout::getLetterAt(double x, double y) const
 159 {
 160     NR::Point point(x, y);
 161
 162     double rotation;
 163     for (iterator it = begin() ; it != end() ; it.nextCharacter()) {
 164         NR::Rect box = characterBoundingBox(it, &rotation);
 165         // todo: rotation
 166         if (box.contains(point)) return it;
 167     }
 168     return end();
 169 }
 170
 171 Layout::iterator Layout::sourceToIterator(void *source_cookie, Glib::ustring::const_iterator text_iterator) const
 172 {
 173     unsigned source_index;
 174     if (_characters.empty()) return end();
 175     for (source_index = 0 ; source_index < _input_stream.size() ; source_index++)
 176         if (_input_stream[source_index]->source_cookie == source_cookie) break;
 177     if (source_index == _input_stream.size()) return end();
 178
 179     unsigned char_index = _sourceToCharacter(source_index);
 180
 181     if (_input_stream[source_index]->Type() != TEXT_SOURCE)
 182         return iterator(this, char_index);
 183
 184     InputStreamTextSource const *text_source = static_cast<InputStreamTextSource const *>(_input_stream[source_index]);
 185     if (text_iterator <= text_source->text_begin) return iterator(this, char_index);
 186     if (text_iterator >= text_source->text_end) {
 187         if (source_index == _input_stream.size() - 1) return end();
 188         return iterator(this, _sourceToCharacter(source_index + 1));
 189     }
 190     Glib::ustring::const_iterator iter_text = text_source->text_begin;
 191     for ( ; char_index < _characters.size() ; char_index++) {
 192         if (iter_text == text_iterator)
 193             return iterator(this, char_index);
 194         iter_text++;
 195     }
 196     return end(); // never happens
 197 }
 198
 199 Layout::iterator Layout::sourceToIterator(void *source_cookie) const
 200 {
 201     return sourceToIterator(source_cookie, Glib::ustring::const_iterator(std::string::const_iterator(NULL)));
 202 }
 203
 204 NR::Rect Layout::glyphBoundingBox(iterator const &it, double *rotation) const
 205 {
 206    if (rotation) *rotation = _glyphs[it._glyph_index].rotation;
 207    return _glyphs[it._glyph_index].span(this).font->BBox(_glyphs[it._glyph_index].glyph);
 208 }
 209
 210 NR::Point Layout::characterAnchorPoint(iterator const &it) const
 211 {
 212     if (_characters.empty())
 213         return _empty_cursor_shape.position;
 214     if (it._char_index == _characters.size()) {
 215         return NR::Point(_chunks.back().left_x + _spans.back().x_end, _lines.back().baseline_y + _spans.back().baseline_shift);
 216     } else {
 217         return NR::Point(_characters[it._char_index].chunk(this).left_x
 218                              + _spans[_characters[it._char_index].in_span].x_start
 219                              + _characters[it._char_index].x,
 220                          _characters[it._char_index].line(this).baseline_y
 221                              + _characters[it._char_index].span(this).baseline_shift);
 222     }
 223 }
 224
 225 NR::Point Layout::chunkAnchorPoint(iterator const &it) const
 226 {
 227     unsigned chunk_index;
 228
 229     if (_chunks.empty())
 230         return NR::Point(0.0, 0.0);
 231
 232     if (_characters.empty())
 233         chunk_index = 0;
 234     else if (it._char_index == _characters.size())
 235         chunk_index = _chunks.size() - 1;
 236     else chunk_index = _characters[it._char_index].span(this).in_chunk;
 237
 238     Alignment alignment = _paragraphs[_lines[_chunks[chunk_index].in_line].in_paragraph].alignment;
 239     if (alignment == LEFT || alignment == FULL)
 240         return NR::Point(_chunks[chunk_index].left_x, _lines[chunk_index].baseline_y);
 241
 242     double chunk_width = _getChunkWidth(chunk_index);
 243     if (alignment == RIGHT)
 244         return NR::Point(_chunks[chunk_index].left_x + chunk_width, _lines[chunk_index].baseline_y);
 245     //centre
 246     return NR::Point(_chunks[chunk_index].left_x + chunk_width * 0.5, _lines[chunk_index].baseline_y);
 247 }
 248
 249 NR::Rect Layout::characterBoundingBox(iterator const &it, double *rotation) const
 250 {
 251     NR::Point top_left, bottom_right;
 252     unsigned char_index = it._char_index;
 253
 254     if (_path_fitted) {
 255         double cluster_half_width = 0.0;
 256         for (int glyph_index = _characters[char_index].in_glyph ; _glyphs[glyph_index].in_character == char_index ; glyph_index++)
 257             cluster_half_width += _glyphs[glyph_index].width;
 258         cluster_half_width *= 0.5;
 259
 260         double midpoint_offset = _characters[char_index].span(this).x_start + _characters[char_index].x + cluster_half_width;
 261         int unused = 0;
 262         Path::cut_position *midpoint_otp = const_cast<Path*>(_path_fitted)->CurvilignToPosition(1, &midpoint_offset, unused);
 263         if (midpoint_offset >= 0.0 && midpoint_otp != NULL && midpoint_otp[0].piece >= 0) {
 264             NR::Point midpoint;
 265             NR::Point tangent;
 266             Span const &span = _characters[char_index].span(this);
 267             double top = span.baseline_shift - span.line_height.ascent;
 268             double bottom = span.baseline_shift + span.line_height.descent;
 269
 270             const_cast<Path*>(_path_fitted)->PointAndTangentAt(midpoint_otp[0].piece, midpoint_otp[0].t, midpoint, tangent);
 271             top_left[NR::X] = midpoint[NR::X] - cluster_half_width;
 272             top_left[NR::Y] = midpoint[NR::Y] + top;
 273             bottom_right[NR::X] = midpoint[NR::X] + cluster_half_width;
 274             bottom_right[NR::Y] = midpoint[NR::Y] + bottom;
 275             if (rotation)
 276                 *rotation = atan2(tangent[1], tangent[0]);
 277         }
 278         g_free(midpoint_otp);
 279     } else {
 280         if (it._char_index == _characters.size()) {
 281             top_left[NR::X] = bottom_right[NR::X] = _chunks.back().left_x + _spans.back().x_end;
 282             char_index--;
 283         } else {
 284             double span_x = _spans[_characters[it._char_index].in_span].x_start + _characters[it._char_index].chunk(this).left_x;
 285             top_left[NR::X] = span_x + _characters[it._char_index].x;
 286             if (it._char_index + 1 == _characters.size() || _characters[it._char_index + 1].in_span != _characters[it._char_index].in_span)
 287                 bottom_right[NR::X] = _spans[_characters[it._char_index].in_span].x_end + _characters[it._char_index].chunk(this).left_x;
 288             else
 289                 bottom_right[NR::X] = span_x + _characters[it._char_index + 1].x;
 290         }
 291
 292         double baseline_y = _characters[char_index].line(this).baseline_y + _characters[char_index].span(this).baseline_shift;
 293         if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
 294             double span_height = _spans[_characters[char_index].in_span].line_height.ascent + _spans[_characters[char_index].in_span].line_height.descent;
 295             top_left[NR::Y] = top_left[NR::X];
 296             top_left[NR::X] = baseline_y - span_height * 0.5;
 297             bottom_right[NR::Y] = bottom_right[NR::X];
 298             bottom_right[NR::X] = baseline_y + span_height * 0.5;
 299         } else {
 300             top_left[NR::Y] = baseline_y - _spans[_characters[char_index].in_span].line_height.ascent;
 301             bottom_right[NR::Y] = baseline_y + _spans[_characters[char_index].in_span].line_height.descent;
 302         }
 303
 304         if (rotation) {
 305             if (it._glyph_index == -1)
 306                 *rotation = 0.0;
 307             else if (it._glyph_index == (int)_glyphs.size())
 308                 *rotation = _glyphs.back().rotation;
 309             else
 310                 *rotation = _glyphs[it._glyph_index].rotation;
 311         }
 312     }
 313
 314     return NR::Rect(top_left, bottom_right);
 315 }
 316
 317 std::vector<NR::Point> Layout::createSelectionShape(iterator const &it_start, iterator const &it_end, NR::Matrix const &transform) const
 318 {
 319     std::vector<NR::Point> quads;
 320     unsigned char_index;
 321     unsigned end_char_index;
 322
 323     if (it_start._char_index < it_end._char_index) {
 324         char_index = it_start._char_index;
 325         end_char_index = it_end._char_index;
 326     } else {
 327         char_index = it_end._char_index;
 328         end_char_index = it_start._char_index;
 329     }
 330     for ( ; char_index < end_char_index ; ) {
 331         if (_characters[char_index].in_glyph == -1) {
 332             char_index++;
 333             continue;
 334         }
 335         double char_rotation = _glyphs[_characters[char_index].in_glyph].rotation;
 336         unsigned span_index = _characters[char_index].in_span;
 337
 338         NR::Point top_left, bottom_right;
 339         if (_path_fitted || char_rotation != 0.0) {
 340             NR::Rect box = characterBoundingBox(iterator(this, char_index), &char_rotation);
 341             top_left = box.min();
 342             bottom_right = box.max();
 343             char_index++;
 344         } else {   // for straight text we can be faster by combining all the character boxes in a span into one box
 345             double span_x = _spans[span_index].x_start + _spans[span_index].chunk(this).left_x;
 346             top_left[NR::X] = span_x + _characters[char_index].x;
 347             while (char_index < end_char_index && _characters[char_index].in_span == span_index)
 348                 char_index++;
 349             if (char_index == _characters.size() || _characters[char_index].in_span != span_index)
 350                 bottom_right[NR::X] = _spans[span_index].x_end + _spans[span_index].chunk(this).left_x;
 351             else
 352                 bottom_right[NR::X] = span_x + _characters[char_index].x;
 353
 354             double baseline_y = _spans[span_index].line(this).baseline_y + _spans[span_index].baseline_shift;
 355             if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
 356                 double span_height = _spans[span_index].line_height.ascent + _spans[span_index].line_height.descent;
 357                 top_left[NR::Y] = top_left[NR::X];
 358                 top_left[NR::X] = baseline_y - span_height * 0.5;
 359                 bottom_right[NR::Y] = bottom_right[NR::X];
 360                 bottom_right[NR::X] = baseline_y + span_height * 0.5;
 361             } else {
 362                 top_left[NR::Y] = baseline_y - _spans[span_index].line_height.ascent;
 363                 bottom_right[NR::Y] = baseline_y + _spans[span_index].line_height.descent;
 364             }
 365         }
 366
 367         NR::Rect char_box(top_left, bottom_right);
 368         if (char_box.extent(NR::X) == 0.0 || char_box.extent(NR::Y) == 0.0)
 369             continue;
 370         NR::Point center_of_rotation((top_left[NR::X] + bottom_right[NR::X]) * 0.5,
 371                                      top_left[NR::Y] + _spans[span_index].line_height.ascent);
 372         NR::Matrix total_transform = NR::translate(-center_of_rotation) * NR::rotate(char_rotation) * NR::translate(center_of_rotation) * transform;
 373         for(int i = 0; i < 4; i ++)
 374             quads.push_back(char_box.corner(i) * total_transform);
 375     }
 376     return quads;
 377 }
 378
 379 void Layout::queryCursorShape(iterator const &it, NR::Point *position, double *height, double *rotation) const
 380 {
 381     if (_characters.empty()) {
 382         *position = _empty_cursor_shape.position;
 383         *height = _empty_cursor_shape.height;
 384         *rotation = _empty_cursor_shape.rotation;
 385     } else {
 386         // we want to cursor to be positioned where the left edge of a character that is about to be typed will be.
 387         // this means x & rotation are the current values but y & height belong to the previous character.
 388         // this isn't quite right because dx attributes will be moved along, but it's good enough
 389         Span const *span;
 390         if (_path_fitted) {
 391             // text on a path
 392             double x;
 393             if (it._char_index >= _characters.size()) {
 394                 span = &_spans.back();
 395                 x = span->x_end + _chunks.back().left_x - _chunks[0].left_x;
 396             } else {
 397                 span = &_spans[_characters[it._char_index].in_span];
 398                 x = _chunks[span->in_chunk].left_x + span->x_start + _characters[it._char_index].x - _chunks[0].left_x;
 399                 if (it._char_index != 0)
 400                     span = &_spans[_characters[it._char_index - 1].in_span];
 401             }
 402             double path_length = const_cast<Path*>(_path_fitted)->Length();
 403             double x_on_path = x;
 404             if (x_on_path < 0.0) x_on_path = 0.0;
 405
 406             int unused = 0;
 407                 // as far as I know these functions are const, they're just not marked as such
 408             Path::cut_position *path_parameter_list = const_cast<Path*>(_path_fitted)->CurvilignToPosition(1, &x_on_path, unused);
 409             Path::cut_position path_parameter;
 410             if (path_parameter_list != NULL && path_parameter_list[0].piece >= 0)
 411                 path_parameter = path_parameter_list[0];
 412             else {
 413                 path_parameter.piece = _path_fitted->descr_cmd.size() - 1;
 414                 path_parameter.t = 0.9999;   // 1.0 will get the wrong tangent
 415             }
 416             g_free(path_parameter_list);
 417
 418             NR::Point point;
 419             NR::Point tangent;
 420             const_cast<Path*>(_path_fitted)->PointAndTangentAt(path_parameter.piece, path_parameter.t, point, tangent);
 421             if (x < 0.0)
 422                 point += x * tangent;
 423             if (x > path_length )
 424                 point += (x - path_length) * tangent;
 425             *rotation = atan2(tangent);
 426             (*position)[NR::X] = point[NR::X] - tangent[NR::Y] * span->baseline_shift;
 427             (*position)[NR::Y] = point[NR::Y] + tangent[NR::X] * span->baseline_shift;
 428         } else {
 429             // text is not on a path
 430             if (it._char_index >= _characters.size()) {
 431                 span = &_spans.back();
 432                 (*position)[NR::X] = _chunks[span->in_chunk].left_x + span->x_end;
 433                 *rotation = _glyphs.empty() ? 0.0 : _glyphs.back().rotation;
 434             } else {
 435                 span = &_spans[_characters[it._char_index].in_span];
 436                 (*position)[NR::X] = _chunks[span->in_chunk].left_x + span->x_start + _characters[it._char_index].x;
 437                 if (it._glyph_index == -1) *rotation = 0.0;
 438                 else if(it._glyph_index == 0) *rotation = _glyphs[0].rotation;
 439                 else *rotation = _glyphs[it._glyph_index - 1].rotation;
 440                 // the first char in a line wants to have the y of the new line, so in that case we don't switch to the previous span
 441                 if (it._char_index != 0 && _characters[it._char_index - 1].chunk(this).in_line == _chunks[span->in_chunk].in_line)
 442                     span = &_spans[_characters[it._char_index - 1].in_span];
 443             }
 444             (*position)[NR::Y] = span->line(this).baseline_y + span->baseline_shift;
 445         }
 446         // up to now *position is the baseline point, not the final point which will be the bottom of the descent
 447         if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
 448             *height = span->line_height.ascent + span->line_height.descent;
 449             *rotation += M_PI / 2;
 450             std::swap((*position)[NR::X], (*position)[NR::Y]);
 451             (*position)[NR::X] -= sin(*rotation) * *height * 0.5;
 452             (*position)[NR::Y] += cos(*rotation) * *height * 0.5;
 453         } else {
 454             double caret_slope_run = 0.0, caret_slope_rise = 1.0;
 455             if (span->font)
 456                 const_cast<font_instance*>(span->font)->FontSlope(caret_slope_run, caret_slope_rise);
 457             double caret_slope = atan2(caret_slope_run, caret_slope_rise);
 458             *height = (span->line_height.ascent + span->line_height.descent) / cos(caret_slope);
 459             *rotation += caret_slope;
 460             (*position)[NR::X] -= sin(*rotation) * span->line_height.descent;
 461             (*position)[NR::Y] += cos(*rotation) * span->line_height.descent;
 462         }
 463     }
 464 }
 465
 466 void Layout::getSourceOfCharacter(iterator const &it, void **source_cookie, Glib::ustring::iterator *text_iterator) const
 467 {
 468     if (it._char_index == _characters.size()) {
 469         *source_cookie = NULL;
 470         return;
 471     }
 472     InputStreamItem *stream_item = _input_stream[_spans[_characters[it._char_index].in_span].in_input_stream_item];
 473     *source_cookie = stream_item->source_cookie;
 474     if (text_iterator && stream_item->Type() == TEXT_SOURCE) {
 475         InputStreamTextSource const *text_source = static_cast<InputStreamTextSource const *>(stream_item);
 476         Glib::ustring::const_iterator text_iter_const = text_source->text_begin;
 477         unsigned char_index = it._char_index;
 478         unsigned original_input_source_index = _spans[_characters[char_index].in_span].in_input_stream_item;
 479         // confusing algorithm because the iterator goes forwards while the index goes backwards.
 480         // It's just that it's faster doing it that way
 481         while (char_index && _spans[_characters[char_index - 1].in_span].in_input_stream_item == original_input_source_index) {
 482             ++text_iter_const;
 483             char_index--;
 484         }
 485         text_source->text->begin().base() + (text_iter_const.base() - text_source->text->begin().base());
 486         *text_iterator = Glib::ustring::iterator(std::string::iterator(const_cast<char*>(&*text_source->text->begin().base() + (text_iter_const.base() - text_source->text->begin().base()))));
 487              // the caller owns the string, so they're going to want a non-const iterator
 488     }
 489 }
 490
 491 void Layout::simulateLayoutUsingKerning(iterator const &from, iterator const &to, OptionalTextTagAttrs *result) const
 492 {
 493     SVGLength zero_length;
 494     zero_length = 0.0;
 495
 496     result->x.clear();
 497     result->y.clear();
 498     result->dx.clear();
 499     result->dy.clear();
 500     result->rotate.clear();
 501     if (to._char_index <= from._char_index)
 502         return;
 503     result->dx.reserve(to._char_index - from._char_index);
 504     result->dy.reserve(to._char_index - from._char_index);
 505     result->rotate.reserve(to._char_index - from._char_index);
 506     for (unsigned char_index = from._char_index ; char_index < to._char_index ; char_index++) {
 507         if (!_characters[char_index].char_attributes.is_char_break)
 508             continue;
 509         if (char_index == 0)
 510             continue;
 511         if (_characters[char_index].chunk(this).in_line != _characters[char_index - 1].chunk(this).in_line)
 512             continue;
 513
 514         unsigned prev_cluster_char_index;
 515         for (prev_cluster_char_index = char_index - 1 ;
 516              prev_cluster_char_index != 0 && !_characters[prev_cluster_char_index].char_attributes.is_cursor_position ;
 517              prev_cluster_char_index--);
 518         if (_characters[char_index].span(this).in_chunk == _characters[char_index - 1].span(this).in_chunk) {
 519             // dx is zero for the first char in a chunk
 520             // this algorithm works by comparing the summed widths of the glyphs with the observed
 521             // difference in x coordinates of characters, and subtracting the two to produce the x kerning.
 522             double glyphs_width = 0.0;
 523             if (_characters[prev_cluster_char_index].in_glyph != -1)
 524                 for (int glyph_index = _characters[prev_cluster_char_index].in_glyph ; glyph_index < _characters[char_index].in_glyph ; glyph_index++)
 525                     glyphs_width += _glyphs[glyph_index].width;
 526             if (_characters[char_index].span(this).direction == RIGHT_TO_LEFT)
 527                 glyphs_width = -glyphs_width;
 528
 529             double dx = (_characters[char_index].x + _characters[char_index].span(this).x_start
 530                          - _characters[prev_cluster_char_index].x - _characters[prev_cluster_char_index].span(this).x_start)
 531                         - glyphs_width;
 532
 533
 534             InputStreamItem *input_item = _input_stream[_characters[char_index].span(this).in_input_stream_item];
 535             if (input_item->Type() == TEXT_SOURCE) {
 536                 SPStyle const *style = static_cast<InputStreamTextSource*>(input_item)->style;
 537                 if (_characters[char_index].char_attributes.is_white)
 538                     dx -= style->word_spacing.computed;
 539                 if (_characters[char_index].char_attributes.is_cursor_position)
 540                     dx -= style->letter_spacing.computed;
 541             }
 542
 543             if (fabs(dx) > 0.0001) {
 544                 result->dx.resize(char_index - from._char_index + 1, zero_length);
 545                 result->dx.back() = dx;
 546             }
 547         }
 548         double dy = _characters[char_index].span(this).baseline_shift - _characters[prev_cluster_char_index].span(this).baseline_shift;
 549         if (fabs(dy) > 0.0001) {
 550             result->dy.resize(char_index - from._char_index + 1, zero_length);
 551             result->dy.back() = dy;
 552         }
 553         if (_characters[char_index].in_glyph != -1 && _glyphs[_characters[char_index].in_glyph].rotation != 0.0) {
 554             result->rotate.resize(char_index - from._char_index + 1, zero_length);
 555             result->rotate.back() = _glyphs[_characters[char_index].in_glyph].rotation;
 556         }
 557     }
 558 }
 559
 560 #define PREV_START_OF_ITEM(this_func)                                                    \
 561     {                                                                                    \
 562         _cursor_moving_vertically = false;                                               \
 563         if (_char_index == 0) return false;                                              \
 564         _char_index--;                                                                   \
 565         return this_func();                                                              \
 566     }
 567 // end of macro
 568
 569 #define THIS_START_OF_ITEM(item_getter)                                                  \
 570     {                                                                                    \
 571         _cursor_moving_vertically = false;                                               \
 572         if (_char_index == 0) return false;                                              \
 573         unsigned original_item;                                                          \
 574         if (_char_index == _parent_layout->_characters.size()) {                         \
 575             _char_index--;                                                               \
 576             original_item = item_getter;                                                 \
 577         } else {                                                                         \
 578             original_item = item_getter;                                                 \
 579             _char_index--;                                                               \
 580         }                                                                                \
 581         while (item_getter == original_item) {                                           \
 582             if (_char_index == 0) {                                                      \
 583                 _glyph_index = _parent_layout->_characters[_char_index].in_glyph;        \
 584                 return true;                                                             \
 585             }                                                                            \
 586             _char_index--;                                                               \
 587         }                                                                                \
 588         _char_index++;                                                                   \
 589         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                \
 590         return true;                                                                     \
 591     }
 592 // end of macro
 593
 594 #define NEXT_START_OF_ITEM(item_getter)                                                  \
 595     {                                                                                    \
 596         _cursor_moving_vertically = false;                                               \
 597         if (_char_index == _parent_layout->_characters.size()) return false;             \
 598         unsigned original_item = item_getter;                                            \
 599         for( ; ; ) {                                                                     \
 600             _char_index++;                                                               \
 601             if (_char_index == _parent_layout->_characters.size()) {                     \
 602                 _glyph_index = _parent_layout->_glyphs.size();                           \
 603                 return false;                                                            \
 604             }                                                                            \
 605             if (item_getter != original_item) break;                                     \
 606         }                                                                                \
 607         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                \
 608         return true;                                                                     \
 609     }
 610 // end of macro
 611
 612 bool Layout::iterator::prevStartOfSpan()
 613     PREV_START_OF_ITEM(thisStartOfSpan);
 614
 615 bool Layout::iterator::thisStartOfSpan()
 616     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].in_span);
 617
 618 bool Layout::iterator::nextStartOfSpan()
 619     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].in_span);
 620
 621
 622 bool Layout::iterator::prevStartOfChunk()
 623     PREV_START_OF_ITEM(thisStartOfChunk);
 624
 625 bool Layout::iterator::thisStartOfChunk()
 626     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_chunk);
 627
 628 bool Layout::iterator::nextStartOfChunk()
 629     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_chunk);
 630
 631
 632 bool Layout::iterator::prevStartOfLine()
 633     PREV_START_OF_ITEM(thisStartOfLine);
 634
 635 bool Layout::iterator::thisStartOfLine()
 636     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].chunk(_parent_layout).in_line);
 637
 638 bool Layout::iterator::nextStartOfLine()
 639     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].chunk(_parent_layout).in_line);
 640
 641
 642 bool Layout::iterator::prevStartOfShape()
 643     PREV_START_OF_ITEM(thisStartOfShape);
 644
 645 bool Layout::iterator::thisStartOfShape()
 646     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_shape);
 647
 648 bool Layout::iterator::nextStartOfShape()
 649     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_shape);
 650
 651
 652 bool Layout::iterator::prevStartOfParagraph()
 653     PREV_START_OF_ITEM(thisStartOfParagraph);
 654
 655 bool Layout::iterator::thisStartOfParagraph()
 656     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_paragraph);
 657
 658 bool Layout::iterator::nextStartOfParagraph()
 659     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_paragraph);
 660
 661
 662 bool Layout::iterator::prevStartOfSource()
 663     PREV_START_OF_ITEM(thisStartOfSource);
 664
 665 bool Layout::iterator::thisStartOfSource()
 666     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_input_stream_item);
 667
 668 bool Layout::iterator::nextStartOfSource()
 669     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_input_stream_item);
 670
 671
 672 bool Layout::iterator::thisEndOfLine()
 673 {
 674     if (_char_index == _parent_layout->_characters.size()) return false;
 675     if (nextStartOfLine())
 676     {
 677         if (_char_index && _parent_layout->_characters[_char_index - 1].char_attributes.is_white)
 678             return prevCursorPosition();
 679         return true;
 680     }
 681     if (_char_index && _parent_layout->_characters[_char_index - 1].chunk(_parent_layout).in_line != _parent_layout->_lines.size() - 1)
 682         return prevCursorPosition();   // for when the last paragraph is empty
 683     return false;
 684 }
 685
 686 void Layout::iterator::beginCursorUpDown()
 687 {
 688     if (_char_index == _parent_layout->_characters.size())
 689         _x_coordinate = _parent_layout->_chunks.back().left_x + _parent_layout->_spans.back().x_end;
 690     else
 691         _x_coordinate = _parent_layout->_characters[_char_index].x + _parent_layout->_characters[_char_index].span(_parent_layout).x_start + _parent_layout->_characters[_char_index].chunk(_parent_layout).left_x;
 692     _cursor_moving_vertically = true;
 693 }
 694
 695 bool Layout::iterator::nextLineCursor()
 696 {
 697     if (!_cursor_moving_vertically)
 698         beginCursorUpDown();
 699     if (_char_index == _parent_layout->_characters.size())
 700         return false;
 701     unsigned line_index = _parent_layout->_characters[_char_index].chunk(_parent_layout).in_line;
 702     if (line_index == _parent_layout->_lines.size() - 1) return false;
 703     if (_parent_layout->_lines[line_index + 1].in_shape != _parent_layout->_lines[line_index].in_shape) {
 704         // switching between shapes: adjust the stored x to compensate
 705         _x_coordinate +=   _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index + 1)].in_chunk].left_x
 706                          - _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index)].in_chunk].left_x;
 707     }
 708     _char_index = _parent_layout->_cursorXOnLineToIterator(line_index + 1, _x_coordinate)._char_index;
 709     _glyph_index = _parent_layout->_characters[_char_index].in_glyph;
 710     return true;
 711 }
 712
 713 bool Layout::iterator::prevLineCursor()
 714 {
 715     if (!_cursor_moving_vertically)
 716         beginCursorUpDown();
 717     unsigned line_index;
 718     if (_char_index == _parent_layout->_characters.size())
 719         line_index = _parent_layout->_lines.size() - 1;
 720     else
 721         line_index = _parent_layout->_characters[_char_index].chunk(_parent_layout).in_line;
 722     if (line_index == 0) return false;
 723     if (_parent_layout->_lines[line_index - 1].in_shape != _parent_layout->_lines[line_index].in_shape) {
 724         // switching between shapes: adjust the stored x to compensate
 725         _x_coordinate +=   _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index - 1)].in_chunk].left_x
 726                          - _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index)].in_chunk].left_x;
 727     }
 728     _char_index = _parent_layout->_cursorXOnLineToIterator(line_index - 1, _x_coordinate)._char_index;
 729     _glyph_index = _parent_layout->_characters[_char_index].in_glyph;
 730     return true;
 731 }
 732
 733 #define NEXT_WITH_ATTRIBUTE_SET(attr)                                                            \
 734     {                                                                                            \
 735         _cursor_moving_vertically = false;                                                       \
 736         for ( ; ; ) {                                                                            \
 737             if (_char_index + 1 >= _parent_layout->_characters.size()) {                         \
 738                 _char_index = _parent_layout->_characters.size();                                \
 739                 _glyph_index = _parent_layout->_glyphs.size();                                   \
 740                 return false;                                                                    \
 741             }                                                                                    \
 742             _char_index++;                                                                       \
 743             if (_parent_layout->_characters[_char_index].char_attributes.attr) break;            \
 744         }                                                                                        \
 745         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                        \
 746         return true;                                                                             \
 747     }
 748 // end of macro
 749
 750 #define PREV_WITH_ATTRIBUTE_SET(attr)                                                            \
 751     {                                                                                            \
 752         _cursor_moving_vertically = false;                                                       \
 753         for ( ; ; ) {                                                                            \
 754             if (_char_index == 0) {                                                              \
 755                 _glyph_index = 0;                                                                \
 756                 return true;                                                                     \
 757             }                                                                                    \
 758             _char_index--;                                                                       \
 759             if (_parent_layout->_characters[_char_index].char_attributes.attr) break;            \
 760         }                                                                                        \
 761         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                        \
 762         return true;                                                                             \
 763     }
 764 // end of macro
 765
 766 bool Layout::iterator::nextCursorPosition()
 767     NEXT_WITH_ATTRIBUTE_SET(is_cursor_position);
 768
 769 bool Layout::iterator::prevCursorPosition()
 770     PREV_WITH_ATTRIBUTE_SET(is_cursor_position);
 771
 772 bool Layout::iterator::nextStartOfWord()
 773     NEXT_WITH_ATTRIBUTE_SET(is_word_start);
 774
 775 bool Layout::iterator::prevStartOfWord()
 776     PREV_WITH_ATTRIBUTE_SET(is_word_start);
 777
 778 bool Layout::iterator::nextEndOfWord()
 779     NEXT_WITH_ATTRIBUTE_SET(is_word_end);
 780
 781 bool Layout::iterator::prevEndOfWord()
 782     PREV_WITH_ATTRIBUTE_SET(is_word_end);
 783
 784 bool Layout::iterator::nextStartOfSentence()
 785     NEXT_WITH_ATTRIBUTE_SET(is_sentence_start);
 786
 787 bool Layout::iterator::prevStartOfSentence()
 788     PREV_WITH_ATTRIBUTE_SET(is_sentence_start);
 789
 790 bool Layout::iterator::nextEndOfSentence()
 791     NEXT_WITH_ATTRIBUTE_SET(is_sentence_end);
 792
 793 bool Layout::iterator::prevEndOfSentence()
 794     PREV_WITH_ATTRIBUTE_SET(is_sentence_end);
 795
 796 bool Layout::iterator::_cursorLeftOrRightLocalX(Direction direction)
 797 {
 798     // the only reason this function is so complicated is to enable visual cursor
 799     // movement moving in to or out of counterdirectional runs
 800     if (_parent_layout->_characters.empty()) return false;
 801     unsigned old_span_index;
 802     Direction old_span_direction;
 803     if (_char_index == _parent_layout->_characters.size())
 804         old_span_index = _parent_layout->_spans.size() - 1;
 805     else
 806         old_span_index = _parent_layout->_characters[_char_index].in_span;
 807     old_span_direction = _parent_layout->_spans[old_span_index].direction;
 808     Direction para_direction = _parent_layout->_spans[old_span_index].paragraph(_parent_layout).base_direction;
 809
 810     int scan_direction;
 811     unsigned old_char_index = _char_index;
 812     if (old_span_direction != para_direction
 813         && ((_char_index == 0 && direction == para_direction)
 814             || (_char_index == _parent_layout->_characters.size() && direction != para_direction))) {
 815         // the end of the text is actually in the middle because of reordering. Do cleverness
 816         scan_direction = direction == para_direction ? +1 : -1;
 817     } else {
 818         if (direction == old_span_direction) {
 819             if (!nextCursorPosition()) return false;
 820         } else {
 821             if (!prevCursorPosition()) return false;
 822         }
 823
 824         unsigned new_span_index = _parent_layout->_characters[_char_index].in_span;
 825         if (new_span_index == old_span_index) return true;
 826         if (old_span_direction != _parent_layout->_spans[new_span_index].direction) {
 827             // we must jump to the other end of a counterdirectional run
 828             scan_direction = direction == para_direction ? +1 : -1;
 829         } else if (_parent_layout->_spans[old_span_index].in_chunk != _parent_layout->_spans[new_span_index].in_chunk) {
 830             // we might have to do a weird jump when we would have crossed a chunk/line break
 831             if (_parent_layout->_spans[old_span_index].line(_parent_layout).in_paragraph != _parent_layout->_spans[new_span_index].line(_parent_layout).in_paragraph)
 832                 return true;
 833             if (old_span_direction == para_direction)
 834                 return true;
 835             scan_direction = direction == para_direction ? +1 : -1;
 836         } else
 837             return true;    // same direction, same chunk: no cleverness required
 838     }
 839
 840     unsigned new_span_index = old_span_index;
 841     for ( ; ; ) {
 842         if (scan_direction > 0) {
 843             if (new_span_index == _parent_layout->_spans.size() - 1) {
 844                 if (_parent_layout->_spans[new_span_index].direction == old_span_direction) {
 845                     _char_index = old_char_index;
 846                     return false;    // the visual end is in the logical middle
 847                 }
 848                 break;
 849             }
 850             new_span_index++;
 851         } else {
 852             if (new_span_index == 0) {
 853                 if (_parent_layout->_spans[new_span_index].direction == old_span_direction) {
 854                     _char_index = old_char_index;
 855                     return false;    // the visual end is in the logical middle
 856                 }
 857                 break;
 858             }
 859             new_span_index--;
 860         }
 861         if (_parent_layout->_spans[new_span_index].direction == para_direction) {
 862             if (para_direction == old_span_direction)
 863                 new_span_index -= scan_direction;
 864             break;
 865         }
 866         if (_parent_layout->_spans[new_span_index].in_chunk != _parent_layout->_spans[old_span_index].in_chunk) {
 867             if (_parent_layout->_spans[old_span_index].line(_parent_layout).in_paragraph == _parent_layout->_spans[new_span_index].line(_parent_layout).in_paragraph
 868                 && para_direction == old_span_direction)
 869                 new_span_index -= scan_direction;
 870             break;
 871         }
 872     }
 873
 874     // found the correct span, now find the correct character
 875     if (_parent_layout->_spans[old_span_index].line(_parent_layout).in_paragraph != _parent_layout->_spans[new_span_index].line(_parent_layout).in_paragraph) {
 876         if (new_span_index > old_span_index)
 877             _char_index = _parent_layout->_spanToCharacter(new_span_index);
 878         else
 879             _char_index = _parent_layout->_spanToCharacter(new_span_index + 1) - 1;
 880     } else {
 881         if (_parent_layout->_spans[new_span_index].direction != direction) {
 882             if (new_span_index >= _parent_layout->_spans.size() - 1)
 883                 _char_index = _parent_layout->_characters.size();
 884             else
 885                 _char_index = _parent_layout->_spanToCharacter(new_span_index + 1) - 1;
 886         } else
 887             _char_index = _parent_layout->_spanToCharacter(new_span_index);
 888     }
 889     if (_char_index == _parent_layout->_characters.size()) {
 890         _glyph_index = _parent_layout->_glyphs.size();
 891         return false;
 892     }
 893     _glyph_index = _parent_layout->_characters[_char_index].in_glyph;
 894     return _char_index != 0;
 895 }
 896
 897 bool Layout::iterator::_cursorLeftOrRightLocalXByWord(Direction direction)
 898 {
 899     bool r;
 900     while ((r = _cursorLeftOrRightLocalX(direction))
 901            && !_parent_layout->_characters[_char_index].char_attributes.is_word_start);
 902     return r;
 903 }
 904
 905 bool Layout::iterator::cursorUp()
 906 {
 907     Direction block_progression = _parent_layout->_blockProgression();
 908     if(block_progression == TOP_TO_BOTTOM)
 909         return prevLineCursor();
 910     else if(block_progression == BOTTOM_TO_TOP)
 911         return nextLineCursor();
 912     else
 913         return _cursorLeftOrRightLocalX(RIGHT_TO_LEFT);
 914 }
 915
 916 bool Layout::iterator::cursorDown()
 917 {
 918     Direction block_progression = _parent_layout->_blockProgression();
 919     if(block_progression == TOP_TO_BOTTOM)
 920         return nextLineCursor();
 921     else if(block_progression == BOTTOM_TO_TOP)
 922         return prevLineCursor();
 923     else
 924         return _cursorLeftOrRightLocalX(LEFT_TO_RIGHT);
 925 }
 926
 927 bool Layout::iterator::cursorLeft()
 928 {
 929     Direction block_progression = _parent_layout->_blockProgression();
 930     if(block_progression == LEFT_TO_RIGHT)
 931         return prevLineCursor();
 932     else if(block_progression == RIGHT_TO_LEFT)
 933         return nextLineCursor();
 934     else
 935         return _cursorLeftOrRightLocalX(RIGHT_TO_LEFT);
 936 }
 937
 938 bool Layout::iterator::cursorRight()
 939 {
 940     Direction block_progression = _parent_layout->_blockProgression();
 941     if(block_progression == LEFT_TO_RIGHT)
 942         return nextLineCursor();
 943     else if(block_progression == RIGHT_TO_LEFT)
 944         return prevLineCursor();
 945     else
 946         return _cursorLeftOrRightLocalX(LEFT_TO_RIGHT);
 947 }
 948
 949 bool Layout::iterator::cursorUpWithControl()
 950 {
 951     Direction block_progression = _parent_layout->_blockProgression();
 952     if(block_progression == TOP_TO_BOTTOM)
 953         return prevStartOfParagraph();
 954     else if(block_progression == BOTTOM_TO_TOP)
 955         return nextStartOfParagraph();
 956     else
 957         return _cursorLeftOrRightLocalXByWord(RIGHT_TO_LEFT);
 958 }
 959
 960 bool Layout::iterator::cursorDownWithControl()
 961 {
 962     Direction block_progression = _parent_layout->_blockProgression();
 963     if(block_progression == TOP_TO_BOTTOM)
 964         return nextStartOfParagraph();
 965     else if(block_progression == BOTTOM_TO_TOP)
 966         return prevStartOfParagraph();
 967     else
 968         return _cursorLeftOrRightLocalXByWord(LEFT_TO_RIGHT);
 969 }
 970
 971 bool Layout::iterator::cursorLeftWithControl()
 972 {
 973     Direction block_progression = _parent_layout->_blockProgression();
 974     if(block_progression == LEFT_TO_RIGHT)
 975         return prevStartOfParagraph();
 976     else if(block_progression == RIGHT_TO_LEFT)
 977         return nextStartOfParagraph();
 978     else
 979         return _cursorLeftOrRightLocalXByWord(RIGHT_TO_LEFT);
 980 }
 981
 982 bool Layout::iterator::cursorRightWithControl()
 983 {
 984     Direction block_progression = _parent_layout->_blockProgression();
 985     if(block_progression == LEFT_TO_RIGHT)
 986         return nextStartOfParagraph();
 987     else if(block_progression == RIGHT_TO_LEFT)
 988         return prevStartOfParagraph();
 989     else
 990         return _cursorLeftOrRightLocalXByWord(LEFT_TO_RIGHT);
 991 }
 992
 993 }//namespace Text
 994 }//namespace Inkscape