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::Maybe<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
 268             const_cast<Path*>(_path_fitted)->PointAndTangentAt(midpoint_otp[0].piece, midpoint_otp[0].t, midpoint, tangent);
 269             top_left[NR::X] = midpoint[NR::X] - cluster_half_width;
 270             top_left[NR::Y] = midpoint[NR::Y] - span.line_height.ascent;
 271             bottom_right[NR::X] = midpoint[NR::X] + cluster_half_width;
 272             bottom_right[NR::Y] = midpoint[NR::Y] + span.line_height.descent;
 273             NR::Point normal = tangent.cw();
 274             top_left += span.baseline_shift * normal;
 275             bottom_right += span.baseline_shift * normal;
 276             if (rotation)
 277                 *rotation = atan2(tangent[1], tangent[0]);
 278         }
 279         g_free(midpoint_otp);
 280     } else {
 281         if (it._char_index == _characters.size()) {
 282             top_left[NR::X] = bottom_right[NR::X] = _chunks.back().left_x + _spans.back().x_end;
 283             char_index--;
 284         } else {
 285             double span_x = _spans[_characters[it._char_index].in_span].x_start + _characters[it._char_index].chunk(this).left_x;
 286             top_left[NR::X] = span_x + _characters[it._char_index].x;
 287             if (it._char_index + 1 == _characters.size() || _characters[it._char_index + 1].in_span != _characters[it._char_index].in_span)
 288                 bottom_right[NR::X] = _spans[_characters[it._char_index].in_span].x_end + _characters[it._char_index].chunk(this).left_x;
 289             else
 290                 bottom_right[NR::X] = span_x + _characters[it._char_index + 1].x;
 291         }
 292
 293         double baseline_y = _characters[char_index].line(this).baseline_y + _characters[char_index].span(this).baseline_shift;
 294         if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
 295             double span_height = _spans[_characters[char_index].in_span].line_height.ascent + _spans[_characters[char_index].in_span].line_height.descent;
 296             top_left[NR::Y] = top_left[NR::X];
 297             top_left[NR::X] = baseline_y - span_height * 0.5;
 298             bottom_right[NR::Y] = bottom_right[NR::X];
 299             bottom_right[NR::X] = baseline_y + span_height * 0.5;
 300         } else {
 301             top_left[NR::Y] = baseline_y - _spans[_characters[char_index].in_span].line_height.ascent;
 302             bottom_right[NR::Y] = baseline_y + _spans[_characters[char_index].in_span].line_height.descent;
 303         }
 304
 305         if (rotation) {
 306             if (it._glyph_index == -1)
 307                 *rotation = 0.0;
 308             else if (it._glyph_index == (int)_glyphs.size())
 309                 *rotation = _glyphs.back().rotation;
 310             else
 311                 *rotation = _glyphs[it._glyph_index].rotation;
 312         }
 313     }
 314
 315     return NR::Rect(top_left, bottom_right);
 316 }
 317
 318 std::vector<NR::Point> Layout::createSelectionShape(iterator const &it_start, iterator const &it_end, NR::Matrix const &transform) const
 319 {
 320     std::vector<NR::Point> quads;
 321     unsigned char_index;
 322     unsigned end_char_index;
 323
 324     if (it_start._char_index < it_end._char_index) {
 325         char_index = it_start._char_index;
 326         end_char_index = it_end._char_index;
 327     } else {
 328         char_index = it_end._char_index;
 329         end_char_index = it_start._char_index;
 330     }
 331     for ( ; char_index < end_char_index ; ) {
 332         if (_characters[char_index].in_glyph == -1) {
 333             char_index++;
 334             continue;
 335         }
 336         double char_rotation = _glyphs[_characters[char_index].in_glyph].rotation;
 337         unsigned span_index = _characters[char_index].in_span;
 338
 339         NR::Point top_left, bottom_right;
 340         if (_path_fitted || char_rotation != 0.0) {
 341             NR::Rect box = characterBoundingBox(iterator(this, char_index), &char_rotation);
 342             top_left = box.min();
 343             bottom_right = box.max();
 344             char_index++;
 345         } else {   // for straight text we can be faster by combining all the character boxes in a span into one box
 346             double span_x = _spans[span_index].x_start + _spans[span_index].chunk(this).left_x;
 347             top_left[NR::X] = span_x + _characters[char_index].x;
 348             while (char_index < end_char_index && _characters[char_index].in_span == span_index)
 349                 char_index++;
 350             if (char_index == _characters.size() || _characters[char_index].in_span != span_index)
 351                 bottom_right[NR::X] = _spans[span_index].x_end + _spans[span_index].chunk(this).left_x;
 352             else
 353                 bottom_right[NR::X] = span_x + _characters[char_index].x;
 354
 355             double baseline_y = _spans[span_index].line(this).baseline_y + _spans[span_index].baseline_shift;
 356             if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
 357                 double span_height = _spans[span_index].line_height.ascent + _spans[span_index].line_height.descent;
 358                 top_left[NR::Y] = top_left[NR::X];
 359                 top_left[NR::X] = baseline_y - span_height * 0.5;
 360                 bottom_right[NR::Y] = bottom_right[NR::X];
 361                 bottom_right[NR::X] = baseline_y + span_height * 0.5;
 362             } else {
 363                 top_left[NR::Y] = baseline_y - _spans[span_index].line_height.ascent;
 364                 bottom_right[NR::Y] = baseline_y + _spans[span_index].line_height.descent;
 365             }
 366         }
 367
 368         NR::Rect char_box(top_left, bottom_right);
 369         if (char_box.extent(NR::X) == 0.0 || char_box.extent(NR::Y) == 0.0)
 370             continue;
 371         NR::Point center_of_rotation((top_left[NR::X] + bottom_right[NR::X]) * 0.5,
 372                                      top_left[NR::Y] + _spans[span_index].line_height.ascent);
 373         NR::Matrix total_transform = NR::translate(-center_of_rotation) * NR::rotate(char_rotation) * NR::translate(center_of_rotation) * transform;
 374         for(int i = 0; i < 4; i ++)
 375             quads.push_back(char_box.corner(i) * total_transform);
 376     }
 377     return quads;
 378 }
 379
 380 void Layout::queryCursorShape(iterator const &it, NR::Point *position, double *height, double *rotation) const
 381 {
 382     if (_characters.empty()) {
 383         *position = _empty_cursor_shape.position;
 384         *height = _empty_cursor_shape.height;
 385         *rotation = _empty_cursor_shape.rotation;
 386     } else {
 387         // we want to cursor to be positioned where the left edge of a character that is about to be typed will be.
 388         // this means x & rotation are the current values but y & height belong to the previous character.
 389         // this isn't quite right because dx attributes will be moved along, but it's good enough
 390         Span const *span;
 391         if (_path_fitted) {
 392             // text on a path
 393             double x;
 394             if (it._char_index >= _characters.size()) {
 395                 span = &_spans.back();
 396                 x = span->x_end + _chunks.back().left_x - _chunks[0].left_x;
 397             } else {
 398                 span = &_spans[_characters[it._char_index].in_span];
 399                 x = _chunks[span->in_chunk].left_x + span->x_start + _characters[it._char_index].x - _chunks[0].left_x;
 400                 if (it._char_index != 0)
 401                     span = &_spans[_characters[it._char_index - 1].in_span];
 402             }
 403             double path_length = const_cast<Path*>(_path_fitted)->Length();
 404             double x_on_path = x;
 405             if (x_on_path < 0.0) x_on_path = 0.0;
 406
 407             int unused = 0;
 408                 // as far as I know these functions are const, they're just not marked as such
 409             Path::cut_position *path_parameter_list = const_cast<Path*>(_path_fitted)->CurvilignToPosition(1, &x_on_path, unused);
 410             Path::cut_position path_parameter;
 411             if (path_parameter_list != NULL && path_parameter_list[0].piece >= 0)
 412                 path_parameter = path_parameter_list[0];
 413             else {
 414                 path_parameter.piece = _path_fitted->descr_cmd.size() - 1;
 415                 path_parameter.t = 0.9999;   // 1.0 will get the wrong tangent
 416             }
 417             g_free(path_parameter_list);
 418
 419             NR::Point point;
 420             NR::Point tangent;
 421             const_cast<Path*>(_path_fitted)->PointAndTangentAt(path_parameter.piece, path_parameter.t, point, tangent);
 422             if (x < 0.0)
 423                 point += x * tangent;
 424             if (x > path_length )
 425                 point += (x - path_length) * tangent;
 426             *rotation = atan2(tangent);
 427             (*position)[NR::X] = point[NR::X] - tangent[NR::Y] * span->baseline_shift;
 428             (*position)[NR::Y] = point[NR::Y] + tangent[NR::X] * span->baseline_shift;
 429         } else {
 430             // text is not on a path
 431             if (it._char_index >= _characters.size()) {
 432                 span = &_spans.back();
 433                 (*position)[NR::X] = _chunks[span->in_chunk].left_x + span->x_end;
 434                 *rotation = _glyphs.empty() ? 0.0 : _glyphs.back().rotation;
 435             } else {
 436                 span = &_spans[_characters[it._char_index].in_span];
 437                 (*position)[NR::X] = _chunks[span->in_chunk].left_x + span->x_start + _characters[it._char_index].x;
 438                 if (it._glyph_index == -1) *rotation = 0.0;
 439                 else if(it._glyph_index == 0) *rotation = _glyphs[0].rotation;
 440                 else *rotation = _glyphs[it._glyph_index - 1].rotation;
 441                 // 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
 442                 if (it._char_index != 0 && _characters[it._char_index - 1].chunk(this).in_line == _chunks[span->in_chunk].in_line)
 443                     span = &_spans[_characters[it._char_index - 1].in_span];
 444             }
 445             (*position)[NR::Y] = span->line(this).baseline_y + span->baseline_shift;
 446         }
 447         // up to now *position is the baseline point, not the final point which will be the bottom of the descent
 448         if (_directions_are_orthogonal(_blockProgression(), TOP_TO_BOTTOM)) {
 449             *height = span->line_height.ascent + span->line_height.descent;
 450             *rotation += M_PI / 2;
 451             std::swap((*position)[NR::X], (*position)[NR::Y]);
 452             (*position)[NR::X] -= sin(*rotation) * *height * 0.5;
 453             (*position)[NR::Y] += cos(*rotation) * *height * 0.5;
 454         } else {
 455             double caret_slope_run = 0.0, caret_slope_rise = 1.0;
 456             if (span->font)
 457                 const_cast<font_instance*>(span->font)->FontSlope(caret_slope_run, caret_slope_rise);
 458             double caret_slope = atan2(caret_slope_run, caret_slope_rise);
 459             *height = (span->line_height.ascent + span->line_height.descent) / cos(caret_slope);
 460             *rotation += caret_slope;
 461             (*position)[NR::X] -= sin(*rotation) * span->line_height.descent;
 462             (*position)[NR::Y] += cos(*rotation) * span->line_height.descent;
 463         }
 464     }
 465 }
 466
 467 void Layout::getSourceOfCharacter(iterator const &it, void **source_cookie, Glib::ustring::iterator *text_iterator) const
 468 {
 469     if (it._char_index == _characters.size()) {
 470         *source_cookie = NULL;
 471         return;
 472     }
 473     InputStreamItem *stream_item = _input_stream[_spans[_characters[it._char_index].in_span].in_input_stream_item];
 474     *source_cookie = stream_item->source_cookie;
 475     if (text_iterator && stream_item->Type() == TEXT_SOURCE) {
 476         InputStreamTextSource const *text_source = static_cast<InputStreamTextSource const *>(stream_item);
 477         Glib::ustring::const_iterator text_iter_const = text_source->text_begin;
 478         unsigned char_index = it._char_index;
 479         unsigned original_input_source_index = _spans[_characters[char_index].in_span].in_input_stream_item;
 480         // confusing algorithm because the iterator goes forwards while the index goes backwards.
 481         // It's just that it's faster doing it that way
 482         while (char_index && _spans[_characters[char_index - 1].in_span].in_input_stream_item == original_input_source_index) {
 483             ++text_iter_const;
 484             char_index--;
 485         }
 486         text_source->text->begin().base() + (text_iter_const.base() - text_source->text->begin().base());
 487         *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()))));
 488              // the caller owns the string, so they're going to want a non-const iterator
 489     }
 490 }
 491
 492 void Layout::simulateLayoutUsingKerning(iterator const &from, iterator const &to, OptionalTextTagAttrs *result) const
 493 {
 494     SVGLength zero_length;
 495     zero_length = 0.0;
 496
 497     result->x.clear();
 498     result->y.clear();
 499     result->dx.clear();
 500     result->dy.clear();
 501     result->rotate.clear();
 502     if (to._char_index <= from._char_index)
 503         return;
 504     result->dx.reserve(to._char_index - from._char_index);
 505     result->dy.reserve(to._char_index - from._char_index);
 506     result->rotate.reserve(to._char_index - from._char_index);
 507     for (unsigned char_index = from._char_index ; char_index < to._char_index ; char_index++) {
 508         if (!_characters[char_index].char_attributes.is_char_break)
 509             continue;
 510         if (char_index == 0)
 511             continue;
 512         if (_characters[char_index].chunk(this).in_line != _characters[char_index - 1].chunk(this).in_line)
 513             continue;
 514
 515         unsigned prev_cluster_char_index;
 516         for (prev_cluster_char_index = char_index - 1 ;
 517              prev_cluster_char_index != 0 && !_characters[prev_cluster_char_index].char_attributes.is_cursor_position ;
 518              prev_cluster_char_index--);
 519         if (_characters[char_index].span(this).in_chunk == _characters[char_index - 1].span(this).in_chunk) {
 520             // dx is zero for the first char in a chunk
 521             // this algorithm works by comparing the summed widths of the glyphs with the observed
 522             // difference in x coordinates of characters, and subtracting the two to produce the x kerning.
 523             double glyphs_width = 0.0;
 524             if (_characters[prev_cluster_char_index].in_glyph != -1)
 525                 for (int glyph_index = _characters[prev_cluster_char_index].in_glyph ; glyph_index < _characters[char_index].in_glyph ; glyph_index++)
 526                     glyphs_width += _glyphs[glyph_index].width;
 527             if (_characters[char_index].span(this).direction == RIGHT_TO_LEFT)
 528                 glyphs_width = -glyphs_width;
 529
 530             double dx = (_characters[char_index].x + _characters[char_index].span(this).x_start
 531                          - _characters[prev_cluster_char_index].x - _characters[prev_cluster_char_index].span(this).x_start)
 532                         - glyphs_width;
 533
 534
 535             InputStreamItem *input_item = _input_stream[_characters[char_index].span(this).in_input_stream_item];
 536             if (input_item->Type() == TEXT_SOURCE) {
 537                 SPStyle const *style = static_cast<InputStreamTextSource*>(input_item)->style;
 538                 if (_characters[char_index].char_attributes.is_white)
 539                     dx -= style->word_spacing.computed;
 540                 if (_characters[char_index].char_attributes.is_cursor_position)
 541                     dx -= style->letter_spacing.computed;
 542             }
 543
 544             if (fabs(dx) > 0.0001) {
 545                 result->dx.resize(char_index - from._char_index + 1, zero_length);
 546                 result->dx.back() = dx;
 547             }
 548         }
 549         double dy = _characters[char_index].span(this).baseline_shift - _characters[prev_cluster_char_index].span(this).baseline_shift;
 550         if (fabs(dy) > 0.0001) {
 551             result->dy.resize(char_index - from._char_index + 1, zero_length);
 552             result->dy.back() = dy;
 553         }
 554         if (_characters[char_index].in_glyph != -1 && _glyphs[_characters[char_index].in_glyph].rotation != 0.0) {
 555             result->rotate.resize(char_index - from._char_index + 1, zero_length);
 556             result->rotate.back() = _glyphs[_characters[char_index].in_glyph].rotation;
 557         }
 558     }
 559 }
 560
 561 #define PREV_START_OF_ITEM(this_func)                                                    \
 562     {                                                                                    \
 563         _cursor_moving_vertically = false;                                               \
 564         if (_char_index == 0) return false;                                              \
 565         _char_index--;                                                                   \
 566         return this_func();                                                              \
 567     }
 568 // end of macro
 569
 570 #define THIS_START_OF_ITEM(item_getter)                                                  \
 571     {                                                                                    \
 572         _cursor_moving_vertically = false;                                               \
 573         if (_char_index == 0) return false;                                              \
 574         unsigned original_item;                                                          \
 575         if (_char_index == _parent_layout->_characters.size()) {                         \
 576             _char_index--;                                                               \
 577             original_item = item_getter;                                                 \
 578         } else {                                                                         \
 579             original_item = item_getter;                                                 \
 580             _char_index--;                                                               \
 581         }                                                                                \
 582         while (item_getter == original_item) {                                           \
 583             if (_char_index == 0) {                                                      \
 584                 _glyph_index = _parent_layout->_characters[_char_index].in_glyph;        \
 585                 return true;                                                             \
 586             }                                                                            \
 587             _char_index--;                                                               \
 588         }                                                                                \
 589         _char_index++;                                                                   \
 590         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                \
 591         return true;                                                                     \
 592     }
 593 // end of macro
 594
 595 #define NEXT_START_OF_ITEM(item_getter)                                                  \
 596     {                                                                                    \
 597         _cursor_moving_vertically = false;                                               \
 598         if (_char_index == _parent_layout->_characters.size()) return false;             \
 599         unsigned original_item = item_getter;                                            \
 600         for( ; ; ) {                                                                     \
 601             _char_index++;                                                               \
 602             if (_char_index == _parent_layout->_characters.size()) {                     \
 603                 _glyph_index = _parent_layout->_glyphs.size();                           \
 604                 return false;                                                            \
 605             }                                                                            \
 606             if (item_getter != original_item) break;                                     \
 607         }                                                                                \
 608         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                \
 609         return true;                                                                     \
 610     }
 611 // end of macro
 612
 613 bool Layout::iterator::prevStartOfSpan()
 614     PREV_START_OF_ITEM(thisStartOfSpan);
 615
 616 bool Layout::iterator::thisStartOfSpan()
 617     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].in_span);
 618
 619 bool Layout::iterator::nextStartOfSpan()
 620     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].in_span);
 621
 622
 623 bool Layout::iterator::prevStartOfChunk()
 624     PREV_START_OF_ITEM(thisStartOfChunk);
 625
 626 bool Layout::iterator::thisStartOfChunk()
 627     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_chunk);
 628
 629 bool Layout::iterator::nextStartOfChunk()
 630     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_chunk);
 631
 632
 633 bool Layout::iterator::prevStartOfLine()
 634     PREV_START_OF_ITEM(thisStartOfLine);
 635
 636 bool Layout::iterator::thisStartOfLine()
 637     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].chunk(_parent_layout).in_line);
 638
 639 bool Layout::iterator::nextStartOfLine()
 640     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].chunk(_parent_layout).in_line);
 641
 642
 643 bool Layout::iterator::prevStartOfShape()
 644     PREV_START_OF_ITEM(thisStartOfShape);
 645
 646 bool Layout::iterator::thisStartOfShape()
 647     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_shape);
 648
 649 bool Layout::iterator::nextStartOfShape()
 650     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_shape);
 651
 652
 653 bool Layout::iterator::prevStartOfParagraph()
 654     PREV_START_OF_ITEM(thisStartOfParagraph);
 655
 656 bool Layout::iterator::thisStartOfParagraph()
 657     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_paragraph);
 658
 659 bool Layout::iterator::nextStartOfParagraph()
 660     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].line(_parent_layout).in_paragraph);
 661
 662
 663 bool Layout::iterator::prevStartOfSource()
 664     PREV_START_OF_ITEM(thisStartOfSource);
 665
 666 bool Layout::iterator::thisStartOfSource()
 667     THIS_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_input_stream_item);
 668
 669 bool Layout::iterator::nextStartOfSource()
 670     NEXT_START_OF_ITEM(_parent_layout->_characters[_char_index].span(_parent_layout).in_input_stream_item);
 671
 672
 673 bool Layout::iterator::thisEndOfLine()
 674 {
 675     if (_char_index == _parent_layout->_characters.size()) return false;
 676     if (nextStartOfLine())
 677     {
 678         if (_char_index && _parent_layout->_characters[_char_index - 1].char_attributes.is_white)
 679             return prevCursorPosition();
 680         return true;
 681     }
 682     if (_char_index && _parent_layout->_characters[_char_index - 1].chunk(_parent_layout).in_line != _parent_layout->_lines.size() - 1)
 683         return prevCursorPosition();   // for when the last paragraph is empty
 684     return false;
 685 }
 686
 687 void Layout::iterator::beginCursorUpDown()
 688 {
 689     if (_char_index == _parent_layout->_characters.size())
 690         _x_coordinate = _parent_layout->_chunks.back().left_x + _parent_layout->_spans.back().x_end;
 691     else
 692         _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;
 693     _cursor_moving_vertically = true;
 694 }
 695
 696 bool Layout::iterator::nextLineCursor()
 697 {
 698     if (!_cursor_moving_vertically)
 699         beginCursorUpDown();
 700     if (_char_index == _parent_layout->_characters.size())
 701         return false;
 702     unsigned line_index = _parent_layout->_characters[_char_index].chunk(_parent_layout).in_line;
 703     if (line_index == _parent_layout->_lines.size() - 1) return false;
 704     if (_parent_layout->_lines[line_index + 1].in_shape != _parent_layout->_lines[line_index].in_shape) {
 705         // switching between shapes: adjust the stored x to compensate
 706         _x_coordinate +=   _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index + 1)].in_chunk].left_x
 707                          - _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index)].in_chunk].left_x;
 708     }
 709     _char_index = _parent_layout->_cursorXOnLineToIterator(line_index + 1, _x_coordinate)._char_index;
 710     _glyph_index = _parent_layout->_characters[_char_index].in_glyph;
 711     return true;
 712 }
 713
 714 bool Layout::iterator::prevLineCursor()
 715 {
 716     if (!_cursor_moving_vertically)
 717         beginCursorUpDown();
 718     unsigned line_index;
 719     if (_char_index == _parent_layout->_characters.size())
 720         line_index = _parent_layout->_lines.size() - 1;
 721     else
 722         line_index = _parent_layout->_characters[_char_index].chunk(_parent_layout).in_line;
 723     if (line_index == 0) return false;
 724     if (_parent_layout->_lines[line_index - 1].in_shape != _parent_layout->_lines[line_index].in_shape) {
 725         // switching between shapes: adjust the stored x to compensate
 726         _x_coordinate +=   _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index - 1)].in_chunk].left_x
 727                          - _parent_layout->_chunks[_parent_layout->_spans[_parent_layout->_lineToSpan(line_index)].in_chunk].left_x;
 728     }
 729     _char_index = _parent_layout->_cursorXOnLineToIterator(line_index - 1, _x_coordinate)._char_index;
 730     _glyph_index = _parent_layout->_characters[_char_index].in_glyph;
 731     return true;
 732 }
 733
 734 #define NEXT_WITH_ATTRIBUTE_SET(attr)                                                            \
 735     {                                                                                            \
 736         _cursor_moving_vertically = false;                                                       \
 737         for ( ; ; ) {                                                                            \
 738             if (_char_index + 1 >= _parent_layout->_characters.size()) {                         \
 739                 _char_index = _parent_layout->_characters.size();                                \
 740                 _glyph_index = _parent_layout->_glyphs.size();                                   \
 741                 return false;                                                                    \
 742             }                                                                                    \
 743             _char_index++;                                                                       \
 744             if (_parent_layout->_characters[_char_index].char_attributes.attr) break;            \
 745         }                                                                                        \
 746         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                        \
 747         return true;                                                                             \
 748     }
 749 // end of macro
 750
 751 #define PREV_WITH_ATTRIBUTE_SET(attr)                                                            \
 752     {                                                                                            \
 753         _cursor_moving_vertically = false;                                                       \
 754         for ( ; ; ) {                                                                            \
 755             if (_char_index == 0) {                                                              \
 756                 _glyph_index = 0;                                                                \
 757                 return false;                                                                    \
 758             }                                                                                    \
 759             _char_index--;                                                                       \
 760             if (_parent_layout->_characters[_char_index].char_attributes.attr) break;            \
 761         }                                                                                        \
 762         _glyph_index = _parent_layout->_characters[_char_index].in_glyph;                        \
 763         return true;                                                                             \
 764     }
 765 // end of macro
 766
 767 bool Layout::iterator::nextCursorPosition()
 768     NEXT_WITH_ATTRIBUTE_SET(is_cursor_position);
 769
 770 bool Layout::iterator::prevCursorPosition()
 771     PREV_WITH_ATTRIBUTE_SET(is_cursor_position);
 772
 773 bool Layout::iterator::nextStartOfWord()
 774     NEXT_WITH_ATTRIBUTE_SET(is_word_start);
 775
 776 bool Layout::iterator::prevStartOfWord()
 777     PREV_WITH_ATTRIBUTE_SET(is_word_start);
 778
 779 bool Layout::iterator::nextEndOfWord()
 780     NEXT_WITH_ATTRIBUTE_SET(is_word_end);
 781
 782 bool Layout::iterator::prevEndOfWord()
 783     PREV_WITH_ATTRIBUTE_SET(is_word_end);
 784
 785 bool Layout::iterator::nextStartOfSentence()
 786     NEXT_WITH_ATTRIBUTE_SET(is_sentence_start);
 787
 788 bool Layout::iterator::prevStartOfSentence()
 789     PREV_WITH_ATTRIBUTE_SET(is_sentence_start);
 790
 791 bool Layout::iterator::nextEndOfSentence()
 792     NEXT_WITH_ATTRIBUTE_SET(is_sentence_end);
 793
 794 bool Layout::iterator::prevEndOfSentence()
 795     PREV_WITH_ATTRIBUTE_SET(is_sentence_end);
 796
 797 bool Layout::iterator::_cursorLeftOrRightLocalX(Direction direction)
 798 {
 799     // the only reason this function is so complicated is to enable visual cursor
 800     // movement moving in to or out of counterdirectional runs
 801     if (_parent_layout->_characters.empty()) return false;
 802     unsigned old_span_index;
 803     Direction old_span_direction;
 804     if (_char_index == _parent_layout->_characters.size())
 805         old_span_index = _parent_layout->_spans.size() - 1;
 806     else
 807         old_span_index = _parent_layout->_characters[_char_index].in_span;
 808     old_span_direction = _parent_layout->_spans[old_span_index].direction;
 809     Direction para_direction = _parent_layout->_spans[old_span_index].paragraph(_parent_layout).base_direction;
 810
 811     int scan_direction;
 812     unsigned old_char_index = _char_index;
 813     if (old_span_direction != para_direction
 814         && ((_char_index == 0 && direction == para_direction)
 815             || (_char_index == _parent_layout->_characters.size() && direction != para_direction))) {
 816         // the end of the text is actually in the middle because of reordering. Do cleverness
 817         scan_direction = direction == para_direction ? +1 : -1;
 818     } else {
 819         if (direction == old_span_direction) {
 820             if (!nextCursorPosition()) return false;
 821         } else {
 822             if (!prevCursorPosition()) return false;
 823         }
 824
 825         unsigned new_span_index = _parent_layout->_characters[_char_index].in_span;
 826         if (new_span_index == old_span_index) return true;
 827         if (old_span_direction != _parent_layout->_spans[new_span_index].direction) {
 828             // we must jump to the other end of a counterdirectional run
 829             scan_direction = direction == para_direction ? +1 : -1;
 830         } else if (_parent_layout->_spans[old_span_index].in_chunk != _parent_layout->_spans[new_span_index].in_chunk) {
 831             // we might have to do a weird jump when we would have crossed a chunk/line break
 832             if (_parent_layout->_spans[old_span_index].line(_parent_layout).in_paragraph != _parent_layout->_spans[new_span_index].line(_parent_layout).in_paragraph)
 833                 return true;
 834             if (old_span_direction == para_direction)
 835                 return true;
 836             scan_direction = direction == para_direction ? +1 : -1;
 837         } else
 838             return true;    // same direction, same chunk: no cleverness required
 839     }
 840
 841     unsigned new_span_index = old_span_index;
 842     for ( ; ; ) {
 843         if (scan_direction > 0) {
 844             if (new_span_index == _parent_layout->_spans.size() - 1) {
 845                 if (_parent_layout->_spans[new_span_index].direction == old_span_direction) {
 846                     _char_index = old_char_index;
 847                     return false;    // the visual end is in the logical middle
 848                 }
 849                 break;
 850             }
 851             new_span_index++;
 852         } else {
 853             if (new_span_index == 0) {
 854                 if (_parent_layout->_spans[new_span_index].direction == old_span_direction) {
 855                     _char_index = old_char_index;
 856                     return false;    // the visual end is in the logical middle
 857                 }
 858                 break;
 859             }
 860             new_span_index--;
 861         }
 862         if (_parent_layout->_spans[new_span_index].direction == para_direction) {
 863             if (para_direction == old_span_direction)
 864                 new_span_index -= scan_direction;
 865             break;
 866         }
 867         if (_parent_layout->_spans[new_span_index].in_chunk != _parent_layout->_spans[old_span_index].in_chunk) {
 868             if (_parent_layout->_spans[old_span_index].line(_parent_layout).in_paragraph == _parent_layout->_spans[new_span_index].line(_parent_layout).in_paragraph
 869                 && para_direction == old_span_direction)
 870                 new_span_index -= scan_direction;
 871             break;
 872         }
 873     }
 874
 875     // found the correct span, now find the correct character
 876     if (_parent_layout->_spans[old_span_index].line(_parent_layout).in_paragraph != _parent_layout->_spans[new_span_index].line(_parent_layout).in_paragraph) {
 877         if (new_span_index > old_span_index)
 878             _char_index = _parent_layout->_spanToCharacter(new_span_index);
 879         else
 880             _char_index = _parent_layout->_spanToCharacter(new_span_index + 1) - 1;
 881     } else {
 882         if (_parent_layout->_spans[new_span_index].direction != direction) {
 883             if (new_span_index >= _parent_layout->_spans.size() - 1)
 884                 _char_index = _parent_layout->_characters.size();
 885             else
 886                 _char_index = _parent_layout->_spanToCharacter(new_span_index + 1) - 1;
 887         } else
 888             _char_index = _parent_layout->_spanToCharacter(new_span_index);
 889     }
 890     if (_char_index == _parent_layout->_characters.size()) {
 891         _glyph_index = _parent_layout->_glyphs.size();
 892         return false;
 893     }
 894     _glyph_index = _parent_layout->_characters[_char_index].in_glyph;
 895     return _char_index != 0;
 896 }
 897
 898 bool Layout::iterator::_cursorLeftOrRightLocalXByWord(Direction direction)
 899 {
 900     bool r;
 901     while ((r = _cursorLeftOrRightLocalX(direction))
 902            && !_parent_layout->_characters[_char_index].char_attributes.is_word_start);
 903     return r;
 904 }
 905
 906 bool Layout::iterator::cursorUp()
 907 {
 908     Direction block_progression = _parent_layout->_blockProgression();
 909     if(block_progression == TOP_TO_BOTTOM)
 910         return prevLineCursor();
 911     else if(block_progression == BOTTOM_TO_TOP)
 912         return nextLineCursor();
 913     else
 914         return _cursorLeftOrRightLocalX(RIGHT_TO_LEFT);
 915 }
 916
 917 bool Layout::iterator::cursorDown()
 918 {
 919     Direction block_progression = _parent_layout->_blockProgression();
 920     if(block_progression == TOP_TO_BOTTOM)
 921         return nextLineCursor();
 922     else if(block_progression == BOTTOM_TO_TOP)
 923         return prevLineCursor();
 924     else
 925         return _cursorLeftOrRightLocalX(LEFT_TO_RIGHT);
 926 }
 927
 928 bool Layout::iterator::cursorLeft()
 929 {
 930     Direction block_progression = _parent_layout->_blockProgression();
 931     if(block_progression == LEFT_TO_RIGHT)
 932         return prevLineCursor();
 933     else if(block_progression == RIGHT_TO_LEFT)
 934         return nextLineCursor();
 935     else
 936         return _cursorLeftOrRightLocalX(RIGHT_TO_LEFT);
 937 }
 938
 939 bool Layout::iterator::cursorRight()
 940 {
 941     Direction block_progression = _parent_layout->_blockProgression();
 942     if(block_progression == LEFT_TO_RIGHT)
 943         return nextLineCursor();
 944     else if(block_progression == RIGHT_TO_LEFT)
 945         return prevLineCursor();
 946     else
 947         return _cursorLeftOrRightLocalX(LEFT_TO_RIGHT);
 948 }
 949
 950 bool Layout::iterator::cursorUpWithControl()
 951 {
 952     Direction block_progression = _parent_layout->_blockProgression();
 953     if(block_progression == TOP_TO_BOTTOM)
 954         return prevStartOfParagraph();
 955     else if(block_progression == BOTTOM_TO_TOP)
 956         return nextStartOfParagraph();
 957     else
 958         return _cursorLeftOrRightLocalXByWord(RIGHT_TO_LEFT);
 959 }
 960
 961 bool Layout::iterator::cursorDownWithControl()
 962 {
 963     Direction block_progression = _parent_layout->_blockProgression();
 964     if(block_progression == TOP_TO_BOTTOM)
 965         return nextStartOfParagraph();
 966     else if(block_progression == BOTTOM_TO_TOP)
 967         return prevStartOfParagraph();
 968     else
 969         return _cursorLeftOrRightLocalXByWord(LEFT_TO_RIGHT);
 970 }
 971
 972 bool Layout::iterator::cursorLeftWithControl()
 973 {
 974     Direction block_progression = _parent_layout->_blockProgression();
 975     if(block_progression == LEFT_TO_RIGHT)
 976         return prevStartOfParagraph();
 977     else if(block_progression == RIGHT_TO_LEFT)
 978         return nextStartOfParagraph();
 979     else
 980         return _cursorLeftOrRightLocalXByWord(RIGHT_TO_LEFT);
 981 }
 982
 983 bool Layout::iterator::cursorRightWithControl()
 984 {
 985     Direction block_progression = _parent_layout->_blockProgression();
 986     if(block_progression == LEFT_TO_RIGHT)
 987         return nextStartOfParagraph();
 988     else if(block_progression == RIGHT_TO_LEFT)
 989         return prevStartOfParagraph();
 990     else
 991         return _cursorLeftOrRightLocalXByWord(LEFT_TO_RIGHT);
 992 }
 993
 994 }//namespace Text
 995 }//namespace Inkscape