bidi.c 121 KB
Newer Older
1
/* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
2
   Copyright (C) 2000-2001, 2004-2005, 2009-2014 Free Software
3
   Foundation, Inc.
Eli Zaretskii's avatar
Eli Zaretskii committed
4 5 6

This file is part of GNU Emacs.

Eli Zaretskii's avatar
Eli Zaretskii committed
7
GNU Emacs is free software: you can redistribute it and/or modify
Eli Zaretskii's avatar
Eli Zaretskii committed
8
it under the terms of the GNU General Public License as published by
Eli Zaretskii's avatar
Eli Zaretskii committed
9 10
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Eli Zaretskii's avatar
Eli Zaretskii committed
11 12 13 14 15 16 17

GNU Emacs is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
Eli Zaretskii's avatar
Eli Zaretskii committed
18
along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
Eli Zaretskii's avatar
Eli Zaretskii committed
19

20 21 22
/* Written by Eli Zaretskii <eliz@gnu.org>.

   A sequential implementation of the Unicode Bidirectional algorithm,
23
   (UBA) as per UAX#9, a part of the Unicode Standard.
Eli Zaretskii's avatar
Eli Zaretskii committed
24

25 26 27 28 29 30 31 32 33 34
   Unlike the Reference Implementation and most other implementations,
   this one is designed to be called once for every character in the
   buffer or string.  That way, we can leave intact the design of the
   Emacs display engine, whereby an iterator object is used to
   traverse buffer or string text character by character, and generate
   the necessary data for displaying each character in 'struct glyph'
   objects.  (See xdisp.c for the details of that iteration.)  The
   functions on this file replace the original linear iteration in the
   logical order of the text with a non-linear iteration in the visual
   order, i.e. in the order characters should be shown on display.
Eli Zaretskii's avatar
Eli Zaretskii committed
35

36
   The main entry point is bidi_move_to_visually_next.  Each time it
Eli Zaretskii's avatar
Eli Zaretskii committed
37 38 39
   is called, it finds the next character in the visual order, and
   returns its information in a special structure.  The caller is then
   expected to process this character for display or any other
40 41 42
   purposes, and call bidi_move_to_visually_next for the next
   character.  See the comments in bidi_move_to_visually_next for more
   details about its algorithm that finds the next visual-order
Eli Zaretskii's avatar
Eli Zaretskii committed
43 44
   character by resolving their levels on the fly.

Eli Zaretskii's avatar
Eli Zaretskii committed
45
   Two other entry points are bidi_paragraph_init and
46 47 48 49
   bidi_mirror_char.  The first determines the base direction of a
   paragraph, while the second returns the mirrored version of its
   argument character.

Eli Zaretskii's avatar
Eli Zaretskii committed
50 51 52 53 54
   A few auxiliary entry points are used to initialize the bidi
   iterator for iterating an object (buffer or string), push and pop
   the bidi iterator state, and save and restore the state of the bidi
   cache.

55 56 57 58
   If you want to understand the code, you will have to read it
   together with the relevant portions of UAX#9.  The comments include
   references to UAX#9 rules, for that very reason.

Eli Zaretskii's avatar
Eli Zaretskii committed
59 60
   A note about references to UAX#9 rules: if the reference says
   something like "X9/Retaining", it means that you need to refer to
Juanma Barranquero's avatar
Juanma Barranquero committed
61
   rule X9 and to its modifications described in the "Implementation
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
   Notes" section of UAX#9, under "Retaining Format Codes".

   Here's the overview of the design of the reordering engine
   implemented by this file.

   Basic implementation structure
   ------------------------------

   The sequential processing steps described by UAX#9 are implemented
   as recursive levels of processing, all of which examine the next
   character in the logical order.  This hierarchy of processing looks
   as follows, from the innermost (deepest) to the outermost level,
   omitting some subroutines used by each level:

     bidi_fetch_char         -- fetch next character
     bidi_resolve_explicit   -- resolve explicit levels and directions
     bidi_resolve_weak       -- resolve weak types
79
     bidi_resolve_brackets   -- resolve "paired brackets" neutral types
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
     bidi_resolve_neutral    -- resolve neutral types
     bidi_level_of_next_char -- resolve implicit levels

   Each level calls the level below it, and works on the result
   returned by the lower level, including all of its sub-levels.

   Unlike all the levels below it, bidi_level_of_next_char can return
   the information about either the next or previous character in the
   logical order, depending on the current direction of scanning the
   buffer or string.  For the next character, it calls all the levels
   below it; for the previous character, it uses the cache, described
   below.

   Thus, the result of calling bidi_level_of_next_char is the resolved
   level of the next or the previous character in the logical order.
   Based on this information, the function bidi_move_to_visually_next
   finds the next character in the visual order and updates the
   direction in which the buffer is scanned, either forward or
   backward, to find the next character to be displayed.  (Text is
   scanned backwards when it needs to be reversed for display, i.e. if
   the visual order is the inverse of the logical order.)  This
   implements the last, reordering steps of the UBA, by successively
   calling bidi_level_of_next_char until the character of the required
   embedding level is found; the scan direction is dynamically updated
   as a side effect.  See the commentary before the 'while' loop in
   bidi_move_to_visually_next, for the details.

   Fetching characters
   -------------------

   In a nutshell, fetching the next character boils down to calling
   STRING_CHAR_AND_LENGTH, passing it the address of a buffer or
   string position.  See bidi_fetch_char.  However, if the next
   character is "covered" by a display property of some kind,
   bidi_fetch_char returns the u+FFFC "object replacement character"
   that represents the entire run of text covered by the display
   property.  (The ch_len and nchars members of 'struct bidi_it'
   reflect the length in bytes and characters of that text.)  This is
   so we reorder text on both sides of the display property as
   appropriate for an image or embedded string.  Similarly, text
   covered by a display spec of the form '(space ...)', is replaced
   with the u+2029 paragraph separator character, so such display
   specs produce the same effect as a TAB under UBA.  Both these
   special characters are not actually displayed -- the display
   property is displayed instead -- but just used to compute the
   embedding level of the surrounding text so as to produce the
   required effect.

   Bidi iterator states
   --------------------

   The UBA is highly context dependent in some of its parts,
   i.e. results of processing a character can generally depend on
   characters very far away.  The UAX#9 description of the UBA
   prescribes a stateful processing of each character, whereby the
   results of this processing depend on various state variables, such
   as the current embedding level, level stack, and directional
   override status.  In addition, the UAX#9 description includes many
   passages like this (from rule W2 in this case):

     Search backward from each instance of a European number until the
     first strong type (R, L, AL, or sos) is found. If an AL is found,
     change the type of the European number to Arabic number.

   To support this, we use a bidi iterator object, 'struct bidi_it',
   which is a sub-structure of 'struct it' used by xdisp.c (see
   dispextern.h for the definition of both of these structures).  The
   bidi iterator holds the entire state of the iteration required by
   the UBA, and is updated as the text is traversed.  In particular,
   the embedding level of the current character being resolved is
   recorded in the iterator state.  To avoid costly searches backward
   in support of rules like W2 above, the necessary character types
   are also recorded in the iterator state as they are found during
   the forward scan, and then used when such rules need to be applied.
   (Forward scans cannot be avoided in this way; they need to be
   performed at least once, and the results recorded in the iterator
   state, to be reused until the forward scan oversteps the recorded
   position.)

   In this manner, the iterator state acts as a mini-cache of
   contextual information required for resolving the level of the
   current character by various UBA rules.

   Caching of bidi iterator states
   -------------------------------

   As described above, the reordering engine uses the information
   recorded in the bidi iterator state in order to resolve the
   embedding level of the current character.  When the reordering
   engine needs to process the next character in the logical order, it
   fetches it and applies to it all the UBA levels, updating the
   iterator state as it goes.  But when the buffer or string is
   scanned backwards, i.e. in the reverse order of buffer/string
   positions, the scanned characters were already processed during the
   preceding forward scan (see bidi_find_other_level_edge).  To avoid
   costly re-processing of characters that were already processed
   during the forward scan, the iterator states computed while
   scanning forward are cached.

   The cache is just a linear array of 'struct bidi_it' objects, which
   is dynamically allocated and reallocated as needed, since the size
   of the cache depends on the text being processed.  We only need the
   cache while processing embedded levels higher than the base
   paragraph embedding level, because these higher levels require
   changes in scan direction.  Therefore, as soon as we are back to
   the base embedding level, we can free the cache; see the calls to
   bidi_cache_reset and bidi_cache_shrink, for the conditions to do
   this.

   The cache maintains the index of the next unused cache slot -- this
   is where the next iterator state will be cached.  The function
   bidi_cache_iterator_state saves an instance of the state in the
   cache and increments the unused slot index.  The companion function
   bidi_cache_find looks up a cached state that corresponds to a given
   buffer/string position.  All of the cached states must correspond
   1:1 to the buffer or string region whose processing they reflect;
   bidi.c will abort if it finds cache slots that violate this 1:1
   correspondence.

   When the parent iterator 'struct it' is pushed (see push_it in
   xdisp.c) to pause the current iteration and start iterating over a
   different object (e.g., a 'display' string that covers some buffer
   text), the bidi iterator cache needs to be "pushed" as well, so
   that a new empty cache could be used while iterating over the new
   object.  Later, when the new object is exhausted, and xdisp.c calls
   pop_it, we need to "pop" the bidi cache as well and return to the
   original cache.  See bidi_push_it and bidi_pop_it for how this is
   done.

   Some functions of the display engine save copies of 'struct it' in
   local variables, and restore them later.  For examples, see
   pos_visible_p and move_it_in_display_line_to in xdisp.c, and
   window_scroll_pixel_based in window.c.  When this happens, we need
   to save and restore the bidi cache as well, because conceptually
   the cache is part of the 'struct it' state, and needs to be in
   perfect sync with the portion of the buffer/string that is being
   processed.  This saving and restoring of the cache state is handled
   by bidi_shelve_cache and bidi_unshelve_cache, and the helper macros
   SAVE_IT and RESTORE_IT defined on xdisp.c.

   Note that, because reordering is implemented below the level in
   xdisp.c that breaks glyphs into screen lines, we are violating
   paragraph 3.4 of UAX#9. which mandates that line breaking shall be
   done before reordering each screen line separately.  However,
   following UAX#9 to the letter in this matter goes against the basic
   design of the Emacs display engine, and so we choose here this
   minor deviation from the UBA letter in preference to redesign of
   the display engine.  The effect of this is only seen in continued
   lines that are broken into screen lines in the middle of a run
   whose direction is opposite to the paragraph's base direction.

   Important design and implementation note: when the code needs to
   scan far ahead, be sure to avoid such scans as much as possible
   when the buffer/string doesn't contain any RTL characters.  Users
   of left-to-right scripts will never forgive you if you introduce
   some slow-down due to bidi in situations that don't involve any
   bidirectional text.  See the large comment near the beginning of
   bidi_resolve_neutral, for one situation where such shortcut was
   necessary.  */
Eli Zaretskii's avatar
Eli Zaretskii committed
239 240 241

#include <config.h>
#include <stdio.h>
242

Eli Zaretskii's avatar
Eli Zaretskii committed
243 244
#include "lisp.h"
#include "character.h"
245
#include "buffer.h"
Eli Zaretskii's avatar
Eli Zaretskii committed
246
#include "dispextern.h"
247
#include "region-cache.h"
Eli Zaretskii's avatar
Eli Zaretskii committed
248

Paul Eggert's avatar
Paul Eggert committed
249
static bool bidi_initialized = 0;
Eli Zaretskii's avatar
Eli Zaretskii committed
250

251
static Lisp_Object bidi_type_table, bidi_mirror_table, bidi_brackets_table;
Eli Zaretskii's avatar
Eli Zaretskii committed
252

253
#define BIDI_EOB   (-1)
Eli Zaretskii's avatar
Eli Zaretskii committed
254 255 256 257 258 259

/* Data type for describing the bidirectional character categories.  */
typedef enum {
  UNKNOWN_BC,
  NEUTRAL,
  WEAK,
260 261
  STRONG,
  EXPLICIT_FORMATTING
Eli Zaretskii's avatar
Eli Zaretskii committed
262 263
} bidi_category_t;

Eli Zaretskii's avatar
Eli Zaretskii committed
264
static Lisp_Object paragraph_start_re, paragraph_separate_re;
265
static Lisp_Object Qparagraph_start, Qparagraph_separate;
Eli Zaretskii's avatar
Eli Zaretskii committed
266

267 268 269 270

/***********************************************************************
			Utilities
 ***********************************************************************/
Eli Zaretskii's avatar
Eli Zaretskii committed
271

272 273
/* Return the bidi type of a character CH, subject to the current
   directional OVERRIDE.  */
274
static bidi_type_t
275
bidi_get_type (int ch, bidi_dir_t override)
Eli Zaretskii's avatar
Eli Zaretskii committed
276
{
277 278
  bidi_type_t default_type;

279 280
  if (ch == BIDI_EOB)
    return NEUTRAL_B;
281
  if (ch < 0 || ch > MAX_CHAR)
282
    emacs_abort ();
283 284

  default_type = (bidi_type_t) XINT (CHAR_TABLE_REF (bidi_type_table, ch));
285 286 287 288 289
  /* Every valid character code, even those that are unassigned by the
     UCD, have some bidi-class property, according to
     DerivedBidiClass.txt file.  Therefore, if we ever get UNKNOWN_BT
     (= zero) code from CHAR_TABLE_REF, that's a bug.  */
  if (default_type == UNKNOWN_BT)
290
    emacs_abort ();
291 292 293

  switch (default_type)
    {
294
      case WEAK_BN:
295 296 297 298 299 300
      case NEUTRAL_B:
      case LRE:
      case LRO:
      case RLE:
      case RLO:
      case PDF:
301 302 303 304
      case LRI:
      case RLI:
      case FSI:
      case PDI:
305
	return default_type;
306
      default:
307 308 309 310 311 312
	if (override == L2R)
	  return STRONG_L;
	else if (override == R2L)
	  return STRONG_R;
	else
	  return default_type;
313
    }
Eli Zaretskii's avatar
Eli Zaretskii committed
314 315
}

316
static void
317 318
bidi_check_type (bidi_type_t type)
{
319
  eassert (UNKNOWN_BT <= type && type <= NEUTRAL_ON);
320 321
}

Eli Zaretskii's avatar
Eli Zaretskii committed
322
/* Given a bidi TYPE of a character, return its category.  */
323
static bidi_category_t
Eli Zaretskii's avatar
Eli Zaretskii committed
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
bidi_get_category (bidi_type_t type)
{
  switch (type)
    {
      case UNKNOWN_BT:
	return UNKNOWN_BC;
      case STRONG_L:
      case STRONG_R:
      case STRONG_AL:
	return STRONG;
      case WEAK_EN:
      case WEAK_ES:
      case WEAK_ET:
      case WEAK_AN:
      case WEAK_CS:
      case WEAK_NSM:
      case WEAK_BN:
	return WEAK;
      case NEUTRAL_B:
      case NEUTRAL_S:
      case NEUTRAL_WS:
      case NEUTRAL_ON:
	return NEUTRAL;
347 348 349 350 351 352 353 354 355 356
      case LRE:
      case LRO:
      case RLE:
      case RLO:
      case PDF:
      case LRI:
      case RLI:
      case FSI:
      case PDI:
	return EXPLICIT_FORMATTING;
Eli Zaretskii's avatar
Eli Zaretskii committed
357
      default:
358
	emacs_abort ();
Eli Zaretskii's avatar
Eli Zaretskii committed
359 360 361
    }
}

362 363 364 365 366 367
static bool
bidi_isolate_fmt_char (bidi_type_t ch_type)
{
  return (ch_type == LRI || ch_type == RLI || ch_type == PDI || ch_type == FSI);
}

368 369 370 371
/* Return the mirrored character of C, if it has one.  If C has no
   mirrored counterpart, return C.
   Note: The conditions in UAX#9 clause L4 regarding the surrounding
   context must be tested by the caller.  */
Eli Zaretskii's avatar
Eli Zaretskii committed
372 373 374
int
bidi_mirror_char (int c)
{
375 376 377 378 379
  Lisp_Object val;

  if (c == BIDI_EOB)
    return c;
  if (c < 0 || c > MAX_CHAR)
380
    emacs_abort ();
Eli Zaretskii's avatar
Eli Zaretskii committed
381

382 383
  val = CHAR_TABLE_REF (bidi_mirror_table, c);
  if (INTEGERP (val))
Eli Zaretskii's avatar
Eli Zaretskii committed
384
    {
385
      int v;
386

387 388
      /* When debugging, check before assigning to V, so that the check
	 isn't broken by undefined behavior due to int overflow.  */
389
      eassert (CHAR_VALID_P (XINT (val)));
390

391 392
      v = XINT (val);

393 394 395
      /* Minimal test we must do in optimized builds, to prevent weird
	 crashes further down the road.  */
      if (v < 0 || v > MAX_CHAR)
396
	emacs_abort ();
397 398

      return v;
Eli Zaretskii's avatar
Eli Zaretskii committed
399
    }
400

Eli Zaretskii's avatar
Eli Zaretskii committed
401 402 403
  return c;
}

404 405 406 407 408 409 410 411 412 413 414 415
/* Return the Bidi_Paired_Bracket_Type property of the character C.  */
static bidi_bracket_type_t
bidi_paired_bracket_type (int c)
{
  if (c == BIDI_EOB)
    return BIDI_BRACKET_NONE;
  if (c < 0 || c > MAX_CHAR)
    emacs_abort ();

  return (bidi_bracket_type_t) XINT (CHAR_TABLE_REF (bidi_brackets_table, c));
}

416
/* Determine the start-of-sequence (sos) directional type given the two
417 418 419
   embedding levels on either side of the run boundary.  Also, update
   the saved info about previously seen characters, since that info is
   generally valid for a single level run.  */
420
static void
421
bidi_set_sos_type (struct bidi_it *bidi_it, int level_before, int level_after)
422
{
423
  int higher_level = (level_before > level_after ? level_before : level_after);
424

425 426
  /* FIXME: should the default sos direction be user selectable?  */
  bidi_it->sos = ((higher_level & 1) != 0 ? R2L : L2R); /* X10 */
427

428 429
  bidi_it->prev.type = UNKNOWN_BT;
  bidi_it->last_strong.type = bidi_it->last_strong.orig_type = UNKNOWN_BT;
430
  bidi_it->prev_for_neutral.type = (bidi_it->sos == R2L ? STRONG_R : STRONG_L);
431
  bidi_it->prev_for_neutral.charpos = bidi_it->charpos;
432
  bidi_it->next_for_neutral.type
433
    = bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
434 435
}

436 437 438
#define ISOLATE_STATUS(BIDI_IT, IDX)  ((BIDI_IT)->level_stack[IDX].flags & 1)
#define OVERRIDE(BIDI_IT, IDX)  (((BIDI_IT)->level_stack[IDX].flags >> 1) & 3)

439 440
/* Push the current embedding level and override status; reset the
   current level to LEVEL and the current override status to OVERRIDE.  */
441
static void
442
bidi_push_embedding_level (struct bidi_it *bidi_it,
443
			   int level, bidi_dir_t override, bool isolate_status)
444
{
445
  struct bidi_stack *st;
446
  int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
447

448
  bidi_it->stack_idx++;
449
  eassert (bidi_it->stack_idx < BIDI_MAXDEPTH+2+1);
450
  st = &bidi_it->level_stack[bidi_it->stack_idx];
451
  eassert (level <= (1 << 7));
452
  st->level = level;
453
  st->flags = (((override & 3) << 1) | (isolate_status != 0));
454 455
  if (isolate_status)
    {
456 457 458 459 460
      st->last_strong_type = bidi_it->last_strong.type;
      st->prev_for_neutral_type = bidi_it->prev_for_neutral.type;
      st->next_for_neutral_type = bidi_it->next_for_neutral.type;
      st->next_for_neutral_pos = bidi_it->next_for_neutral.charpos;
      st->flags |= ((bidi_it->sos == L2R ? 0 : 1) << 3);
461
    }
462 463 464
  /* We've got a new isolating sequence, compute the directional type
     of sos and initialize per-sequence variables (UAX#9, clause X10).  */
  bidi_set_sos_type (bidi_it, prev_level, level);
465 466
}

467 468 469
/* Pop from the stack the embedding level, the directional override
   status, and optionally saved information for the isolating run
   sequence.  Return the new level.  */
470
static int
471 472
bidi_pop_embedding_level (struct bidi_it *bidi_it)
{
473 474
  int level;

475 476
  /* UAX#9 says to ignore invalid PDFs (X7, last bullet)
     and PDIs (X6a, 2nd bullet).  */
477
  if (bidi_it->stack_idx > 0)
478
    {
479
      bool isolate_status = ISOLATE_STATUS (bidi_it, bidi_it->stack_idx);
480 481
      int old_level = bidi_it->level_stack[bidi_it->stack_idx].level;

482 483 484 485 486
      struct bidi_stack st;

      st = bidi_it->level_stack[bidi_it->stack_idx];
      if (isolate_status)
	{
487
	  bidi_dir_t sos = ((st.flags >> 3) & 1);
488 489 490 491 492 493 494
	  /* PREV is used in W1 for resolving WEAK_NSM.  By the time
	     we get to an NSM, we must have gotten past at least one
	     character: the PDI that ends the isolate from which we
	     are popping here.  So PREV will have been filled up by
	     the time we first use it.  We initialize it here to
	     UNKNOWN_BT to be able to catch any blunders in this
	     logic.  */
495
	  bidi_it->prev.orig_type = bidi_it->prev.type = UNKNOWN_BT;
496 497 498 499 500
	  bidi_it->last_strong.type = st.last_strong_type;
	  bidi_it->prev_for_neutral.type = st.prev_for_neutral_type;
	  bidi_it->next_for_neutral.type = st.next_for_neutral_type;
	  bidi_it->next_for_neutral.charpos = st.next_for_neutral_pos;
	  bidi_it->sos = (sos == 0 ? L2R : R2L);
501
	}
502 503 504 505
      else
	bidi_set_sos_type (bidi_it, old_level,
			   bidi_it->level_stack[bidi_it->stack_idx - 1].level);

506 507
      bidi_it->stack_idx--;
    }
508 509 510
  level = bidi_it->level_stack[bidi_it->stack_idx].level;
  eassert (0 <= level && level <= BIDI_MAXDEPTH + 1);
  return level;
511 512 513
}

/* Record in SAVED_INFO the information about the current character.  */
514
static void
515
bidi_remember_char (struct bidi_saved_info *saved_info,
516
		    struct bidi_it *bidi_it, bool from_type)
517 518
{
  saved_info->charpos = bidi_it->charpos;
519 520 521 522 523
  if (from_type)
    saved_info->type = bidi_it->type;
  else
    saved_info->type = bidi_it->type_after_wn;
  bidi_check_type (saved_info->type);
524
  saved_info->orig_type = bidi_it->orig_type;
525
  bidi_check_type (saved_info->orig_type);
526 527
}

Eli Zaretskii's avatar
Eli Zaretskii committed
528 529
/* Copy the bidi iterator from FROM to TO.  To save cycles, this only
   copies the part of the level stack that is actually in use.  */
530
static void
Eli Zaretskii's avatar
Eli Zaretskii committed
531 532
bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
{
Paul Eggert's avatar
Paul Eggert committed
533 534 535 536 537
  /* Copy everything from the start through the active part of
     the level stack.  */
  memcpy (to, from,
	  (offsetof (struct bidi_it, level_stack[1])
	   + from->stack_idx * sizeof from->level_stack[0]));
Eli Zaretskii's avatar
Eli Zaretskii committed
538 539
}

540 541 542 543

/***********************************************************************
			Caching the bidi iterator states
 ***********************************************************************/
Eli Zaretskii's avatar
Eli Zaretskii committed
544

545 546 547
/* We allocate and de-allocate the cache in chunks of this size (in
   characters).  200 was chosen as an upper limit for reasonably-long
   lines in a text file/buffer.  */
548
#define BIDI_CACHE_CHUNK 200
549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572
/* Maximum size we allow the cache to become, per iterator stack slot,
   in units of struct bidi_it size.  If we allow unlimited growth, we
   could run out of memory for pathologically long bracketed text or
   very long text lines that need to be reordered.  This is aggravated
   when word-wrap is in effect, since then functions display_line and
   move_it_in_display_line_to need to keep up to 4 copies of the
   cache.

   This limitation means there can be no more than that amount of
   contiguous RTL text on any single physical line in a LTR paragraph,
   and similarly with contiguous LTR + numeric text in a RTL
   paragraph.  (LTR text in a LTR paragraph and RTL text in a RTL
   paragraph are not reordered, and so don't need the cache, and
   cannot hit this limit.)  More importantly, no single line can have
   text longer than this inside paired brackets (because bracket pairs
   resolution uses the cache).  If the limit is exceeded, the fallback
   code will produce visual order that will be incorrect if there are
   RTL characters in the offending line of text.  */
/* Do we need to allow customization of this limit?  */
#define BIDI_CACHE_MAX_ELTS_PER_SLOT 50000
#if BIDI_CACHE_CHUNK >= BIDI_CACHE_MAX_ELTS_PER_SLOT
# error BIDI_CACHE_CHUNK must be less than BIDI_CACHE_MAX_ELTS_PER_SLOT
#endif
static ptrdiff_t bidi_cache_max_elts = BIDI_CACHE_MAX_ELTS_PER_SLOT;
573
static struct bidi_it *bidi_cache;
574
static ptrdiff_t bidi_cache_size = 0;
575
enum { elsz = sizeof (struct bidi_it) };
576 577 578
static ptrdiff_t bidi_cache_idx;	/* next unused cache slot */
static ptrdiff_t bidi_cache_last_idx;	/* slot of last cache hit */
static ptrdiff_t bidi_cache_start = 0;	/* start of cache for this
579 580
					   "stack" level */

Paul Eggert's avatar
Paul Eggert committed
581 582 583 584 585 586 587 588 589
/* 5-slot stack for saving the start of the previous level of the
   cache.  xdisp.c maintains a 5-slot stack for its iterator state,
   and we need the same size of our stack.  */
static ptrdiff_t bidi_cache_start_stack[IT_STACK_SIZE];
static int bidi_cache_sp;

/* Size of header used by bidi_shelve_cache.  */
enum
  {
590 591 592
    bidi_shelve_header_size
      = (sizeof (bidi_cache_idx) + sizeof (bidi_cache_start_stack)
	 + sizeof (bidi_cache_sp) + sizeof (bidi_cache_start)
593
	 + sizeof (bidi_cache_last_idx) + sizeof (bidi_cache_max_elts))
Paul Eggert's avatar
Paul Eggert committed
594 595
  };

596 597 598 599 600 601 602
/* Effectively remove the cached states beyond the Nth state from the
   part of the cache relevant to iteration of the current object
   (buffer or string).  */
static void
bidi_cache_reset_to (int n)
{
  bidi_cache_idx = bidi_cache_start + n;
603
  bidi_cache_last_idx = -1;
604 605
}

606 607 608 609 610 611
/* Reset the cache state to the empty state.  We only reset the part
   of the cache relevant to iteration of the current object.  Previous
   objects, which are pushed on the display iterator's stack, are left
   intact.  This is called when the cached information is no more
   useful for the current iteration, e.g. when we were reseated to a
   new position on the same object.  */
612
static void
Eli Zaretskii's avatar
Eli Zaretskii committed
613 614
bidi_cache_reset (void)
{
615
  bidi_cache_reset_to (0);
Eli Zaretskii's avatar
Eli Zaretskii committed
616 617
}

618 619 620 621
/* Shrink the cache to its minimal size.  Called when we init the bidi
   iterator for reordering a buffer or a string that does not come
   from display properties, because that means all the previously
   cached info is of no further use.  */
622
static void
623 624 625 626
bidi_cache_shrink (void)
{
  if (bidi_cache_size > BIDI_CACHE_CHUNK)
    {
627
      bidi_cache = xrealloc (bidi_cache, BIDI_CACHE_CHUNK * elsz);
628
      bidi_cache_size = BIDI_CACHE_CHUNK;
629 630
    }
  bidi_cache_reset ();
631
  bidi_cache_max_elts = BIDI_CACHE_MAX_ELTS_PER_SLOT;
632 633
}

634
static void
635
bidi_cache_fetch_state (ptrdiff_t idx, struct bidi_it *bidi_it)
Eli Zaretskii's avatar
Eli Zaretskii committed
636 637 638
{
  int current_scan_dir = bidi_it->scan_dir;

639
  if (idx < bidi_cache_start || idx >= bidi_cache_idx)
640
    emacs_abort ();
Eli Zaretskii's avatar
Eli Zaretskii committed
641 642 643 644 645 646 647

  bidi_copy_it (bidi_it, &bidi_cache[idx]);
  bidi_it->scan_dir = current_scan_dir;
  bidi_cache_last_idx = idx;
}

/* Find a cached state with a given CHARPOS and resolved embedding
648
   level less or equal to LEVEL.  If LEVEL is -1, disregard the
Eli Zaretskii's avatar
Eli Zaretskii committed
649
   resolved levels in cached states.  DIR, if non-zero, means search
650 651 652
   in that direction from the last cache hit.

   Value is the index of the cached state, or -1 if not found.  */
653
static ptrdiff_t
654
bidi_cache_search (ptrdiff_t charpos, int level, int dir)
Eli Zaretskii's avatar
Eli Zaretskii committed
655
{
656
  ptrdiff_t i, i_start;
Eli Zaretskii's avatar
Eli Zaretskii committed
657

658
  if (bidi_cache_idx > bidi_cache_start)
Eli Zaretskii's avatar
Eli Zaretskii committed
659
    {
660 661
      if (bidi_cache_last_idx == -1)
	bidi_cache_last_idx = bidi_cache_idx - 1;
Eli Zaretskii's avatar
Eli Zaretskii committed
662
      if (charpos < bidi_cache[bidi_cache_last_idx].charpos)
663 664 665 666 667 668 669 670 671 672 673
	{
	  dir = -1;
	  i_start = bidi_cache_last_idx - 1;
	}
      else if (charpos > (bidi_cache[bidi_cache_last_idx].charpos
			  + bidi_cache[bidi_cache_last_idx].nchars - 1))
	{
	  dir = 1;
	  i_start = bidi_cache_last_idx + 1;
	}
      else if (dir)
Eli Zaretskii's avatar
Eli Zaretskii committed
674 675 676 677 678 679 680 681 682 683
	i_start = bidi_cache_last_idx;
      else
	{
	  dir = -1;
	  i_start = bidi_cache_idx - 1;
	}

      if (dir < 0)
	{
	  /* Linear search for now; FIXME!  */
684
	  for (i = i_start; i >= bidi_cache_start; i--)
685 686
	    if (bidi_cache[i].charpos <= charpos
		&& charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
Eli Zaretskii's avatar
Eli Zaretskii committed
687 688 689 690 691 692
		&& (level == -1 || bidi_cache[i].resolved_level <= level))
	      return i;
	}
      else
	{
	  for (i = i_start; i < bidi_cache_idx; i++)
693 694
	    if (bidi_cache[i].charpos <= charpos
		&& charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
Eli Zaretskii's avatar
Eli Zaretskii committed
695 696 697 698 699 700 701 702 703 704 705
		&& (level == -1 || bidi_cache[i].resolved_level <= level))
	      return i;
	}
    }

  return -1;
}

/* Find a cached state where the resolved level changes to a value
   that is lower than LEVEL, and return its cache slot index.  DIR is
   the direction to search, starting with the last used cache slot.
706
   If DIR is zero, we search backwards from the last occupied cache
Paul Eggert's avatar
Paul Eggert committed
707
   slot.  BEFORE means return the index of the slot that
708
   is ``before'' the level change in the search direction.  That is,
Eli Zaretskii's avatar
Eli Zaretskii committed
709 710 711 712 713 714 715 716
   given the cached levels like this:

	 1122333442211
	  AB        C

   and assuming we are at the position cached at the slot marked with
   C, searching backwards (DIR = -1) for LEVEL = 2 will return the
   index of slot B or A, depending whether BEFORE is, respectively,
Paul Eggert's avatar
Paul Eggert committed
717
   true or false.  */
718
static ptrdiff_t
Paul Eggert's avatar
Paul Eggert committed
719
bidi_cache_find_level_change (int level, int dir, bool before)
Eli Zaretskii's avatar
Eli Zaretskii committed
720 721 722
{
  if (bidi_cache_idx)
    {
723
      ptrdiff_t i = dir ? bidi_cache_last_idx : bidi_cache_idx - 1;
Eli Zaretskii's avatar
Eli Zaretskii committed
724 725
      int incr = before ? 1 : 0;

726 727
      if (i < 0)  /* cache overflowed? */
	i = 0;
728

Eli Zaretskii's avatar
Eli Zaretskii committed
729 730 731 732 733 734 735
      if (!dir)
	dir = -1;
      else if (!incr)
	i += dir;

      if (dir < 0)
	{
736
	  while (i >= bidi_cache_start + incr)
Eli Zaretskii's avatar
Eli Zaretskii committed
737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758
	    {
	      if (bidi_cache[i - incr].resolved_level >= 0
		  && bidi_cache[i - incr].resolved_level < level)
		return i;
	      i--;
	    }
	}
      else
	{
	  while (i < bidi_cache_idx - incr)
	    {
	      if (bidi_cache[i + incr].resolved_level >= 0
		  && bidi_cache[i + incr].resolved_level < level)
		return i;
	      i++;
	    }
	}
    }

  return -1;
}

759
static void
760
bidi_cache_ensure_space (ptrdiff_t idx)
761 762 763 764
{
  /* Enlarge the cache as needed.  */
  if (idx >= bidi_cache_size)
    {
765
      ptrdiff_t chunk_size = BIDI_CACHE_CHUNK;
766

767 768
      if (bidi_cache_size > bidi_cache_max_elts - chunk_size)
	chunk_size = bidi_cache_max_elts - bidi_cache_size;
769

770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791
      if (max (idx + 1,
	       bidi_cache_size + chunk_size) <= bidi_cache_max_elts)
	{
	  /* The bidi cache cannot be larger than the largest Lisp
	     string or buffer.  */
	  ptrdiff_t string_or_buffer_bound
	    = max (BUF_BYTES_MAX, STRING_BYTES_BOUND);

	  /* Also, it cannot be larger than what C can represent.  */
	  ptrdiff_t c_bound
	    = (min (PTRDIFF_MAX, SIZE_MAX) - bidi_shelve_header_size) / elsz;
	  ptrdiff_t max_elts = bidi_cache_max_elts;

	  max_elts = min (max_elts, min (string_or_buffer_bound, c_bound));

	  /* Force xpalloc not to over-allocate by passing it MAX_ELTS
	     as its 4th argument.  */
	  bidi_cache = xpalloc (bidi_cache, &bidi_cache_size,
				max (chunk_size, idx - bidi_cache_size + 1),
				max_elts, elsz);
	  eassert (bidi_cache_size > idx);
	}
792 793 794
    }
}

795
static int
796 797
bidi_cache_iterator_state (struct bidi_it *bidi_it, bool resolved,
			   bool update_only)
Eli Zaretskii's avatar
Eli Zaretskii committed
798
{
799
  ptrdiff_t idx;
Eli Zaretskii's avatar
Eli Zaretskii committed
800 801 802

  /* We should never cache on backward scans.  */
  if (bidi_it->scan_dir == -1)
803
    emacs_abort ();
Eli Zaretskii's avatar
Eli Zaretskii committed
804 805
  idx = bidi_cache_search (bidi_it->charpos, -1, 1);

806
  if (idx < 0 && update_only)
807
    return 0;
808

Eli Zaretskii's avatar
Eli Zaretskii committed
809 810 811
  if (idx < 0)
    {
      idx = bidi_cache_idx;
812
      bidi_cache_ensure_space (idx);
813 814 815
      /* Character positions should correspond to cache positions 1:1.
	 If we are outside the range of cached positions, the cache is
	 useless and must be reset.  */
816 817 818 819
      if (bidi_cache_start < idx && idx < bidi_cache_size
	  && (bidi_it->charpos > (bidi_cache[idx - 1].charpos
				  + bidi_cache[idx - 1].nchars)
	      || bidi_it->charpos < bidi_cache[bidi_cache_start].charpos))
820 821
	{
	  bidi_cache_reset ();
822
	  idx = bidi_cache_start;
823
	}
824
      if (bidi_it->nchars <= 0)
825
	emacs_abort ();
826 827 828 829 830 831 832
      /* Don't cache if no available space in the cache.  */
      if (bidi_cache_size > idx)
	{
	  bidi_copy_it (&bidi_cache[idx], bidi_it);
	  if (!resolved)
	    bidi_cache[idx].resolved_level = -1;
	}
Eli Zaretskii's avatar
Eli Zaretskii committed
833 834 835 836 837 838
    }
  else
    {
      /* Copy only the members which could have changed, to avoid
	 costly copying of the entire struct.  */
      bidi_cache[idx].type = bidi_it->type;
839
      bidi_check_type (bidi_it->type);
840 841
      bidi_cache[idx].type_after_wn = bidi_it->type_after_wn;
      bidi_check_type (bidi_it->type_after_wn);
Eli Zaretskii's avatar
Eli Zaretskii committed
842 843 844 845 846 847 848
      if (resolved)
	bidi_cache[idx].resolved_level = bidi_it->resolved_level;
      else
	bidi_cache[idx].resolved_level = -1;
      bidi_cache[idx].invalid_levels = bidi_it->invalid_levels;
      bidi_cache[idx].next_for_neutral = bidi_it->next_for_neutral;
      bidi_cache[idx].next_for_ws = bidi_it->next_for_ws;
Eli Zaretskii's avatar
Eli Zaretskii committed
849
      bidi_cache[idx].disp_pos = bidi_it->disp_pos;
850
      bidi_cache[idx].disp_prop = bidi_it->disp_prop;
851 852
      bidi_cache[idx].bracket_pairing_pos = bidi_it->bracket_pairing_pos;
      bidi_cache[idx].bracket_enclosed_type = bidi_it->bracket_enclosed_type;
Eli Zaretskii's avatar
Eli Zaretskii committed
853 854
    }

855 856 857 858 859 860 861 862 863 864 865 866 867
  if (bidi_cache_size > idx)
    {
      bidi_cache_last_idx = idx;
      if (idx >= bidi_cache_idx)
	bidi_cache_idx = idx + 1;
      return 1;
    }
  else
    {
      /* The cache overflowed.  */
      bidi_cache_last_idx = -1;
      return 0;
    }
Eli Zaretskii's avatar
Eli Zaretskii committed
868 869
}

870 871
/* Look for a cached iterator state that corresponds to CHARPOS.  If
   found, copy the cached state into BIDI_IT and return the type of
872
   the cached entry.  If not found, return UNKNOWN_BT.  RESOLVED_ONLY
873
   zero means it is OK to return cached states that were not fully
874 875
   resolved yet.  This can happen if the state was cached before it
   was resolved in bidi_resolve_neutral.  */
876
static bidi_type_t
877
bidi_cache_find (ptrdiff_t charpos, bool resolved_only, struct bidi_it *bidi_it)
Eli Zaretskii's avatar
Eli Zaretskii committed
878
{
879
  ptrdiff_t i = bidi_cache_search (charpos, -1, bidi_it->scan_dir);
Eli Zaretskii's avatar
Eli Zaretskii committed
880

881
  if (i >= bidi_cache_start
882 883 884 885 886 887
      && (!resolved_only
	  /* Callers that want only fully resolved states (and set
	     resolved_only = true) need to be sure that there's enough
	     info in the cached state to return the state as final,
	     and if not, they don't want the cached state.  */
	  || bidi_cache[i].resolved_level >= 0))
Eli Zaretskii's avatar
Eli Zaretskii committed
888 889 890
    {
      bidi_dir_t current_scan_dir = bidi_it->scan_dir;

891
      bidi_copy_it (bidi_it, &bidi_cache[i]);
Eli Zaretskii's avatar
Eli Zaretskii committed
892
      bidi_cache_last_idx = i;
893
      /* Don't let scan direction from the cached state override
Eli Zaretskii's avatar
Eli Zaretskii committed
894 895 896 897 898 899 900 901
	 the current scan direction.  */
      bidi_it->scan_dir = current_scan_dir;
      return bidi_it->type;
    }

  return UNKNOWN_BT;
}

902
static int
Eli Zaretskii's avatar
Eli Zaretskii committed
903 904
bidi_peek_at_next_level (struct bidi_it *bidi_it)
{
905
  if (bidi_cache_idx == bidi_cache_start)
906
    emacs_abort ();
907 908 909 910 911
  /* If the cache overflowed, return the level of the last cached
     character.  */
  if (bidi_cache_last_idx == -1
      || (bidi_cache_last_idx >= bidi_cache_idx - 1 && bidi_it->scan_dir > 0))
    return bidi_cache[bidi_cache_idx - 1].resolved_level;
Eli Zaretskii's avatar
Eli Zaretskii committed
912 913 914
  return bidi_cache[bidi_cache_last_idx + bidi_it->scan_dir].resolved_level;
}

915 916 917 918 919 920 921

/***********************************************************************
	     Pushing and popping the bidi iterator state
 ***********************************************************************/

/* Push the bidi iterator state in preparation for reordering a
   different object, e.g. display string found at certain buffer
922 923 924
   position.  Pushing the bidi iterator boils down to saving its
   entire state on the cache and starting a new cache "stacked" on top
   of the current cache.  */
925 926
void
bidi_push_it (struct bidi_it *bidi_it)
Eli Zaretskii's avatar
Eli Zaretskii committed
927
{
928 929
  /* Give this stack slot its cache room.  */
  bidi_cache_max_elts += BIDI_CACHE_MAX_ELTS_PER_SLOT;
930 931 932
  /* Save the current iterator state in its entirety after the last
     used cache slot.  */
  bidi_cache_ensure_space (bidi_cache_idx);
933
  bidi_cache[bidi_cache_idx++] = *bidi_it;
934

935
  /* Push the current cache start onto the stack.  */
936
  eassert (bidi_cache_sp < IT_STACK_SIZE);
937
  bidi_cache_start_stack[bidi_cache_sp++] = bidi_cache_start;
938

939 940 941 942 943 944 945 946 947 948 949
  /* Start a new level of cache, and make it empty.  */
  bidi_cache_start = bidi_cache_idx;
  bidi_cache_last_idx = -1;
}

/* Restore the iterator state saved by bidi_push_it and return the
   cache to the corresponding state.  */
void
bidi_pop_it (struct bidi_it *bidi_it)
{
  if (bidi_cache_start <= 0)
950
    emacs_abort ();
951 952 953 954 955 956

  /* Reset the next free cache slot index to what it was before the
     call to bidi_push_it.  */
  bidi_cache_idx = bidi_cache_start - 1;

  /* Restore the bidi iterator state saved in the cache.  */
957
  *bidi_it = bidi_cache[bidi_cache_idx];
958 959 960

  /* Pop the previous cache start from the stack.  */
  if (bidi_cache_sp <= 0)
961
    emacs_abort ();
962 963 964 965
  bidi_cache_start = bidi_cache_start_stack[--bidi_cache_sp];

  /* Invalidate the last-used cache slot data.  */
  bidi_cache_last_idx = -1;
966 967 968

  bidi_cache_max_elts -= BIDI_CACHE_MAX_ELTS_PER_SLOT;
  eassert (bidi_cache_max_elts > 0);
969 970
}

971
static ptrdiff_t bidi_cache_total_alloc;
972

973 974 975 976 977
/* Stash away a copy of the cache and its control variables.  */
void *
bidi_shelve_cache (void)
{
  unsigned char *databuf;
Paul Eggert's avatar
Paul Eggert committed
978
  ptrdiff_t alloc;
979

980
  /* Empty cache.  */
981 982 983
  if (bidi_cache_idx == 0)
    return NULL;

Paul Eggert's avatar
Paul Eggert committed
984 985 986 987
  alloc = (bidi_shelve_header_size
	   + bidi_cache_idx * sizeof (struct bidi_it));
  databuf = xmalloc (alloc);
  bidi_cache_total_alloc += alloc;
988

989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007
  memcpy (databuf, &bidi_cache_idx, sizeof (bidi_cache_idx));
  memcpy (databuf + sizeof (bidi_cache_idx),
	  bidi_cache, bidi_cache_idx * sizeof (struct bidi_it));
  memcpy (databuf + sizeof (bidi_cache_idx)
	  + bidi_cache_idx * sizeof (struct bidi_it),
	  bidi_cache_start_stack, sizeof (bidi_cache_start_stack));
  memcpy (databuf + sizeof (bidi_cache_idx)
	  + bidi_cache_idx * sizeof (struct bidi_it)
	  + sizeof (bidi_cache_start_stack),
	  &bidi_cache_sp, sizeof (bidi_cache_sp));
  memcpy (databuf + sizeof (bidi_cache_idx)
	  + bidi_cache_idx * sizeof (struct bidi_it)
	  + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
	  &bidi_cache_start, sizeof (bidi_cache_start));
  memcpy (databuf + sizeof (bidi_cache_idx)
	  + bidi_cache_idx * sizeof (struct bidi_it)
	  + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
	  + sizeof (bidi_cache_start),
	  &bidi_cache_last_idx, sizeof (bidi_cache_last_idx));
1008 1009 1010 1011 1012
  memcpy (databuf + sizeof (bidi_cache_idx)
	  + bidi_cache_idx * sizeof (struct bidi_it)
	  + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
	  + sizeof (bidi_cache_start) + sizeof (bidi_cache_last_idx),
	  &bidi_cache_max_elts, sizeof (bidi_cache_max_elts));
1013 1014 1015 1016

  return databuf;
}

1017 1018
/* Restore the cache state from a copy stashed away by
   bidi_shelve_cache, and free the buffer used to stash that copy.
Paul Eggert's avatar
Paul Eggert committed
1019
   JUST_FREE means free the buffer, but don't restore the
1020 1021
   cache; used when the corresponding iterator is discarded instead of
   being restored.  */
1022
void
Paul Eggert's avatar
Paul Eggert committed
1023
bidi_unshelve_cache (void *databuf, bool just_free)
1024 1025 1026 1027
{
  unsigned char *p = databuf;

  if (!p)
1028
    {
1029 1030 1031 1032 1033
      if (!just_free)
	{
	  /* A NULL pointer means an empty cache.  */
	  bidi_cache_start = 0;
	  bidi_cache_sp = 0;
1034
	  bidi_cache_max_elts = BIDI_CACHE_MAX_ELTS_PER_SLOT;
1035 1036
	  bidi_cache_reset ();
	}
1037
    }
1038 1039
  else
    {
1040 1041 1042 1043 1044
      if (just_free)
	{
	  ptrdiff_t idx;

	  memcpy (&idx, p, sizeof (bidi_cache_idx));
1045 1046
	  bidi_cache_total_alloc
	    -= bidi_shelve_header_size + idx * sizeof (struct bidi_it);
1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073
	}
      else
	{
	  memcpy (&bidi_cache_idx, p, sizeof (bidi_cache_idx));
	  bidi_cache_ensure_space (bidi_cache_idx);
	  memcpy (bidi_cache, p + sizeof (bidi_cache_idx),
		  bidi_cache_idx * sizeof (struct bidi_it));
	  memcpy (bidi_cache_start_stack,
		  p + sizeof (bidi_cache_idx)
		  + bidi_cache_idx * sizeof (struct bidi_it),
		  sizeof (bidi_cache_start_stack));
	  memcpy (&bidi_cache_sp,
		  p + sizeof (bidi_cache_idx)
		  + bidi_cache_idx * sizeof (struct bidi_it)
		  + sizeof (bidi_cache_start_stack),
		  sizeof (bidi_cache_sp));
	  memcpy (&bidi_cache_start,
		  p + sizeof (bidi_cache_idx)
		  + bidi_cache_idx * sizeof (struct bidi_it)
		  + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
		  sizeof (bidi_cache_start));
	  memcpy (&bidi_cache_last_idx,
		  p + sizeof (bidi_cache_idx)
		  + bidi_cache_idx * sizeof (struct bidi_it)
		  + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
		  + sizeof (bidi_cache_start),
		  sizeof (bidi_cache_last_idx));
1074 1075 1076 1077 1078