Bug #1924


ArrayIndexOutOfBounds in Chain.ChainIterator

Added by Michael Kay over 10 years ago. Updated over 10 years ago.

Start date:
Due date:
% Done:


Estimated time:
Legacy ID:
Applies to branch:
Fix Committed on Branch:
Fixed in Maintenance Release:


One of the data structures used for implementing a Sequence in Saxon is the "Chain" structure. This is used in cases where (cursory) static analysis suggests that appending/prepending to the sequence is a likely operation. The data structure is therefore optimized for appending/prepending items, at the cost of finding items by position. If there is then an attempt to find an item by position, the data structure is consolidated to make this efficient. This is intended to work well for situations where a sequence is built incrementally, one item at a time, and is then processed using direct access (integer subscripting). However, the operation of consolidating the structure does not take account of the fact that there might be open iterators working on the original linked list. When the chain is consolidated, a subsequent use of such an iterator is liable to crash. Note that this does not require multi-threading, because it is quite possible for multiple iterators to be active on the same structure even within a single thread.

Actions #1

Updated by Michael Kay over 10 years ago

  • Status changed from New to Resolved

I have committed a fix which stores the "consolidated" (array) form of the sequence alongside the linked list, rather than replacing the linked list. There's a memory cost to this, incurred only the first time direct addressing is attempted, but it gives both fast append, fast iteration, and fast direct access.

Actions #2

Updated by O'Neil Delpratt over 10 years ago

  • Status changed from Resolved to Closed
  • % Done changed from 0 to 100
  • Fixed in version set to

Big fix applied in the Saxon maintenance release.

Please register to edit this issue

Also available in: Atom PDF