1 package frost.core
2
3 uses frost.unsafe.Pointer
4
5 ---------------
6 -- IMPORTANT --
7 ------------------------------------------------------------------------------
8 -- String and MutableString are assumed to have a compatible memory layout! --
9 -- See MutableString.finish(). --
10 ------------------------------------------------------------------------------
11
12 ====================================================================================================
13 A mutable variant of `String`.
14 ====================================================================================================
15 class MutableString {
16 ================================================================================================
17 Represents the position of a Unicode codepoint within a `MutableString`.
18 ================================================================================================
19 class Index : Value, HashKey<Index>, Comparable<Index> {
20 def byteOffset:Int
21
22 init(byteOffset:Int) {
23 self.byteOffset := byteOffset
24 }
25
26 @override
27 function =(other:Index):Bit {
28 return byteOffset = other.byteOffset
29 }
30
31 @override
32 function >(other:Index):Bit {
33 return byteOffset > other.byteOffset
34 }
35
36 @override
37 function get_hash():Int {
38 return byteOffset
39 }
40 }
41
42 @private
43 class UTF8List : List<Char8> {
44 def str:MutableString
45
46 init(str:MutableString) {
47 self.str := str
48 }
49
50 @override
51 function [](index:Int):Char8 {
52 return str.data[index]
53 }
54
55 @override
56 method []:=(index:Int, value:Char8) {
57 str.data[index] := value
58 }
59
60 @override
61 method add(c:Char8) {
62 str.append(c)
63 }
64
65 @override
66 method insert(index:Int, c:Char8) {
67 -- FIXME performance
68 str[index .. index] := c.toString
69 }
70
71 @override
72 method removeIndex(index:Int):Char8 {
73 -- FIXME performance
74 def result := str.data[index]
75 str[index ... index] := ""
76 return result
77 }
78
79 @override
80 function get_count():Int {
81 return str._length
82 }
83
84 @override
85 function get_iterator():Iterator<Char8> {
86 return UTF8Iterator(str)
87 }
88
89 @override
90 method clear() {
91 str.clear()
92 }
93 }
94
95 @private
96 class UTF8Iterator : Iterator<Char8> {
97 var index := 0
98
99 def str:MutableString
100
101 init(str:MutableString) {
102 self.str := str
103 }
104
105 @override
106 function get_done():Bit {
107 return index >= str._length
108 }
109
110 @override
111 method next():Char8 {
112 index += 1
113 return str.data[index - 1]
114 }
115 }
116
117 ================================================================================================
118 A view of the UTF8 bytes this string contains.
119 ================================================================================================
120 property utf8:List<Char8>
121 function get_utf8():List<Char8> {
122 return UTF8List(self)
123 }
124
125 ================================================================================================
126 The number of Unicode codepoints this string contains. As the string is internally stored in the
127 variable-width UTF8 format, determining the length of the string takes an amount of time
128 proportional to the number of characters it contains.
129 ================================================================================================
130 property length:Int
131
132 ================================================================================================
133 The number of UTF8 bytes this string contains.
134 ================================================================================================
135 property byteLength:Int
136
137 ================================================================================================
138 An `Index` representing the beginning of the string.
139 ================================================================================================
140 property start:Index
141
142 ================================================================================================
143 An `Index` representing the end of the string.
144 ================================================================================================
145 property end:Index
146
147 @private
148 constant DEFAULT_SIZE := 32
149
150 @private
151 var data:Pointer<Char8>
152
153 @private
154 var _length:Int
155
156 @private
157 var maxLength:Int
158
159 -- for binary compatibility with String
160 @private
161 var dummy:String?
162
163 ================================================================================================
164 Creates an empty `MutableString`.
165 ================================================================================================
166 init() {
167 init(DEFAULT_SIZE)
168 }
169
170 ================================================================================================
171 Creates a `MutableString` initially containing the same characters as the specified `String`.
172 ================================================================================================
173 @unsafeAccess
174 init(s:String) {
175 _length := s._length
176 maxLength := _length + DEFAULT_SIZE
177 data := Pointer<Char8>.alloc(maxLength)
178 for i in 0 .. s._length {
179 -- FIXME performance need memcpy
180 data[i] := s.data[i]
181 }
182 }
183
184 ================================================================================================
185 Creates an empty `MutableString` with the specified initial capacity. The `MutableString` will
186 contain zero characters, but allocate enough storage to hold `capacity` characters, and thus not
187 need to perform any reallocation until reaching that size.
188 ================================================================================================
189 init(capacity:Int) {
190 _length := 0
191 maxLength := capacity
192 data := Pointer<Char8>.alloc(maxLength)
193 }
194
195 @override
196 @private
197 method cleanup() {
198 data.destroy()
199 }
200
201 ================================================================================================
202 Appends the specified character to the end of this string.
203 ================================================================================================
204 -- FIXME @self
205 method append(c:Char8) {
206 ensureCapacity(_length + 1)
207 data[_length] := c
208 _length += 1
209 }
210
211 ================================================================================================
212 Appends the specified character to the end of this string.
213 ================================================================================================
214 -- FIXME @self
215 method append(c:Char32) {
216 def value := c.asInt32
217 if value < 0x80< 0x80 {
218 ensureCapacity(_length + 1)
219 data[_length] := c.toChar8
220 _length += 1
221 }
222 else if value < 0x800< 0x800 {
223 ensureCapacity(_length + 2)
224 data[_length + 0] := Char8((value >> 6 || 0b11000000).asUInt8)
225 data[_length + 1] := Char8((value && 0b111111 || 0b10000000).asUInt8)
226 _length += 2
227 }
228 else if value < 0x10000< 0x10000 {
229 ensureCapacity(_length + 3)
230 data[_length + 0] := Char8((value >> 12 || 0b11100000).asUInt8)
231 data[_length + 1] := Char8((value >> 6 && 0b111111 || 0b10000000).asUInt8)
232 data[_length + 2] := Char8((value && 0b111111 || 0b10000000).asUInt8)
233 _length += 3
234 }
235 else {
236 ensureCapacity(_length + 4)
237 data[_length + 0] := Char8((value >> 18 || 0b11110000).asUInt8)
238 data[_length + 1] := Char8((value >> 12 && 0b111111 || 0b10000000).asUInt8)
239 data[_length + 2] := Char8((value >> 6 && 0b111111 || 0b10000000).asUInt8)
240 data[_length + 3] := Char8((value && 0b111111 || 0b10000000).asUInt8)
241 _length += 4
242 }
243 }
244
245 ================================================================================================
246 Appends the specified string to the end of this string.
247 ================================================================================================
248 -- FIXME @self
249 @unsafeAccess
250 method append(s:String) {
251 ensureCapacity(_length + s._length)
252 for i in 0 .. s._length {
253 data[_length + i] := s.data[i]
254 }
255 _length += s._length
256 }
257
258 ================================================================================================
259 Appends the specified characters to the end of this string.
260 ================================================================================================
261 -- FIXME @self
262 method append(chars:Pointer<Char8>, count:Int) {
263 ensureCapacity(_length + count)
264 for i in 0 .. count {
265 data[_length + i] := chars[i]
266 }
267 _length += count
268 }
269
270 -- FIXME @self
271 method append(o:Object) {
272 append(o.toString)
273 }
274
275 ================================================================================================
276 Returns the number of Unicode codepoints in the string. Note that because the string is
277 internally stored in the variable-length UTF-8 encoding, determining the number of Unicode
278 codepoints in the string can be a relatively expensive operation for long strings (linear with
279 respect to the size of the string).
280 ================================================================================================
281 function get_length():Int {
282 var result := 0
283 var index := start
284 while index != end {
285 index := next(index)
286 result += 1
287 }
288 return result
289 }
290
291 ================================================================================================
292 Returns the number of bytes of storage taken up by this string's internal UTF-8 encoding.
293 ================================================================================================
294 function get_byteLength():Int {
295 return _length
296 }
297
298 ================================================================================================
299 Returns the index of the first character in the string.
300 ================================================================================================
301 function get_start():Index {
302 return Index(0)
303 }
304
305 ================================================================================================
306 Returns the index just past the end of the string.
307 ================================================================================================
308 function get_end():Index {
309 return Index(_length)
310 }
311
312 ================================================================================================
313 Returns the index of the Unicode codepoint after the given index. It is an error to call
314 `next()` when already at the end of the string. Note that because a logical character can
315 consist of multiple Unicode codepoints (such as LATIN SMALL LETTER A followed by COMBINING ACUTE
316 ACCENT), this may return an index in the middle of such a compound character.
317 ================================================================================================
318 function next(i:Index):Index {
319 assert i.byteOffset < _length
320 def< _length
321 def c := data[i.byteOffset].asInt && 0xFF
322 if c >= 0b11110000 {
323 return Index(i.byteOffset + 4)
324 }
325 if c >= 0b11100000 {
326 return Index(i.byteOffset + 3)
327 }
328 if c >= 0b11000000 {
329 return Index(i.byteOffset + 2)
330 }
331 return Index(i.byteOffset + 1)
332 }
333
334 ================================================================================================
335 Returns the index of the Unicode codepoint before the given index. It is an error to call
336 `previous()` when already at the beginning of the string. Note that because a logical character
337 can consist of multiple Unicode codepoints (such as LATIN SMALL LETTER A followed by COMBINING
338 ACUTE ACCENT), this may return an index in the middle of such a compound character.
339 ================================================================================================
340 function previous(i:Index):Index {
341 assert i.byteOffset > 0
342 var newValue := i.byteOffset - 1
343 while data[newValue].asInt && 0xFF >= 0b10000000 &
344 data[newValue].asInt && 0xFF < 0b11000000 {
345 newValue -= 1
346 }
347 return Index(newValue)
348 }
349
350 ================================================================================================
351 Returns the index offset by `offset` Unicode codepoints. It is an error to index before the
352 beginning or after the end of the string. Note that because a logical character can consist of
353 multiple Unicode codepoints (such as LATIN SMALL LETTER A followed by COMBINING ACUTE ACCENT),
354 this may return an index in the middle of such a compound character.
355 ================================================================================================
356 function offset(index:Index, offset:Int):Index {
357 var result := index
358 if offset > 0 {
359 for i in 0 .. offset {
360 result := next(result)
361 }
362 }
363 else {
364 for i in 0 .. offset by -1 {
365 result := previous(result)
366 }
367 }
368 return result
369 }
370
371 ================================================================================================
372 Returns the index of the first occurrence of the string `s` within this string, or `null` if not
373 found.
374
375 @param s the string to search for
376 @returns the index of the match, or `null` if not found
377 ================================================================================================
378 function indexOf(s:String):Index? {
379 return indexOf(s, start)
380 }
381
382 ================================================================================================
383 Returns the index of the first occurrence of the string `s` within this string, starting from
384 the specified `index`, or `null` if not found.
385
386 @param s the string to search for
387 @param start the index to begin searching from
388 @returns the index of the match, or `null` if not found
389 ================================================================================================
390 @unsafeAccess
391 function indexOf(s:String, start:Index):Index? {
392 if _length < s._length {< s._length {
393 return null
394 }
395 outer: for i in start.byteOffset ... _length - s._length {
396 for j in 0 .. s._length {
397 if data[i + j] != s.data[j] {
398 continue outer
399 }
400 }
401 return Index(i)
402 }
403 return null
404 }
405
406 ================================================================================================
407 Returns `true` if this string contains at least one occurrence of the given character.
408 ================================================================================================
409 function contains(c:Char8):Bit {
410 for i in 0 .. _length {
411 if data[i] = c {
412 return true
413 }
414 }
415 return false
416 }
417
418 ================================================================================================
419 Returns `true` if this string contains at least one occurrence of the given substring.
420 ================================================================================================
421 function contains(s:String):Bit {
422 return indexOf(s) !== null
423 }
424
425 ================================================================================================
426 Returns `true` if this string begins with `other`.
427 ================================================================================================
428 @unsafeAccess
429 function startsWith(other:String):Bit {
430 if _length < other._length {< other._length {
431 return false
432 }
433 for i in 0 .. other._length {
434 if data[i] != other.data[i] {
435 return false
436 }
437 }
438 return true
439 }
440
441 ================================================================================================
442 Returns `true` if this string ends with `other`.
443 ================================================================================================
444 @unsafeAccess
445 function endsWith(other:String):Bit {
446 if _length < other._length {< other._length {
447 return false
448 }
449 for i in 0 .. other._length {
450 if data[_length - other._length + i] != other.data[i] {
451 return false
452 }
453 }
454 return true
455 }
456
457 ================================================================================================
458 Returns the index of the last occurrence of the string `s` within this string, or `null` if not
459 found.
460
461 @param s the string to search for
462 @returns the index of the match, or `null` if not found
463 ================================================================================================
464 function lastIndexOf(s:String):Index? {
465 return lastIndexOf(s, end)
466 }
467
468 ================================================================================================
469 Returns the index of the last occurrence of the string `s` within this string, starting the
470 search backwards from the specified `index`, or `null` if not found.
471
472 @param s the string to search for
473 @param start the index to begin searching from
474 @returns the index of the match, or `null` if not found
475 ================================================================================================
476 @unsafeAccess
477 function lastIndexOf(s:String, start:Index):Index? {
478 if _length < s._length {< s._length {
479 return null
480 }
481 def startPos := start.byteOffset.min(_length - s._length)
482 outer: for i in startPos ... 0 by -1 {
483 for j in 0 .. s._length {
484 if data[i + j] != s.data[j] {
485 continue outer
486 }
487 }
488 return Index(i)
489 }
490 return null
491 }
492
493 ================================================================================================
494 Returns `true` if this string matches the given regular expression. The regular expression must
495 match the entire string.
496
497 @param regex the regular expression to compare against
498 @returns `true` if the string matches
499 ================================================================================================
500 function matches(regex:RegularExpression):Bit {
501 return regex.matcher(toString).matches()
502 }
503
504 ================================================================================================
505 Returns `true` if this string contains a match for the given regular expression. The regular
506 expression may match zero or more characters of the string, starting at any point.
507
508 @param needle the regular expression to search for
509 @returns `true` if the string contains a match
510 ================================================================================================
511 function contains(needle:RegularExpression):Bit {
512 return needle.matcher(toString).find()
513 }
514
515 ================================================================================================
516 Removes whitespace from the beginning and end of this string.
517 ================================================================================================
518 -- FIXME @self
519 method trim() {
520 var i := start
521 while i != end & self[i].isWhitespace {
522 i := next(i)
523 }
524 self[start .. i] := ""
525 if _length = 0 {
526 return
527 }
528 i := previous(end)
529 while i != start & self[i].isWhitespace {
530 i := previous(i)
531 }
532 self[next(i)..] := ""
533 }
534
535 -- FIXME @self
536 method replace(search:RegularExpression, replacement:String) {
537 replace(search, replacement, true)
538 }
539
540 -- FIXME @self
541 method replace(search:RegularExpression, replacement:String, allowGroupReferences:Bit) {
542 def matcher := search.matcher(toString)
543 clear()
544 while matcher.find() {
545 matcher.appendReplacement(self, replacement, allowGroupReferences)
546 }
547 matcher.appendTail(self)
548 }
549
550 ================================================================================================
551 Searches the string for a regular expression, replacing occurrences of the regular expression
552 with new text determined by a function. For instance, given:
553
554 -- testcase MutableStringReplace(PrintLine)
555 "This is a test!".replace(/\w+/, word => word.length)
556
557 The regular expression `/\w+/` matches sequences of one or more word characters; in other words,
558 it matches all words occurring in the string. The replacement function `word => word.length`
559 replaces each matched sequence with the number of characters in the sequence, resulting in the
560 text:
561
562 4 2 1 4!
563
564 @param search the regular expression to match the string with
565 @param replacement a function generating the replacement text
566 ================================================================================================
567 -- FIXME @self
568 method replace(search:RegularExpression, replacement:(String)=>(Object)) {
569 def matcher := search.matcher(toString)
570 clear()
571 while matcher.find() {
572 matcher.appendReplacement(self, replacement(matcher.group(0)).toString, false)
573 }
574 matcher.appendTail(self)
575 }
576
577 method replace(search:RegularExpression, replacement:(String)=&>(Object)) {
578 def matcher := search.matcher(toString)
579 clear()
580 while matcher.find() {
581 matcher.appendReplacement(self, replacement(matcher.group(0)).toString, false)
582 }
583 matcher.appendTail(self)
584 }
585
586 ================================================================================================
587 As [replace(RegularExpression, (String)=>(Object))], but the replacement function receives the
588 capture groups from the regular expression rather than the raw matched text. The groups list
589 includes the special whole-match group at index `0`, with the first set of parentheses in the
590 regular expression corresponding to index `1`.
591
592 @param search the regular expression to match the string with
593 @param replacement a function generating the replacement text
594 ================================================================================================
595 -- FIXME @self
596 method replace(search:RegularExpression, replacement:(ListView<String?>)=>(Object)) {
597 def matcher := search.matcher(toString)
598 clear()
599 while matcher.find() {
600 def groups := Array<String?>()
601 for i in 0 .. matcher.get_groupCount() {
602 groups.add(matcher.group(i))
603 }
604 matcher.appendReplacement(self, replacement(groups).toString, false)
605 }
606 matcher.appendTail(self)
607 }
608
609 method replace(search:RegularExpression, replacement:(ListView<String?>)=&>(Object)) {
610 def matcher := search.matcher(toString)
611 clear()
612 while matcher.find() {
613 def groups := Array<String?>()
614 for i in 0 .. matcher.get_groupCount() {
615 groups.add(matcher.group(i))
616 }
617 matcher.appendReplacement(self, replacement(groups).toString, false)
618 }
619 matcher.appendTail(self)
620 }
621
622 ================================================================================================
623 Returns the Unicode codepoint at the given offset within the string.
624 ================================================================================================
625 function [](index:Index):Char32 {
626 def idx := index.byteOffset
627 def c := data[idx]
628 var result := c.asInt32
629 if c.asInt && 0xFF < 0b11000000 {
630 return Char32(result)
631 }
632 if c.asInt && 0xFF < 0b11100000 {
633 assert idx + 1 < _length
634 result := result && 0b11111 << 6 + data[idx + 1].asInt32 && 0b111111
635 return Char32(result)
636 }
637 if c.asInt && 0xFF < 0b11110000 {
638 assert idx + 2 < _length
639 result := result && 0b1111 << 12 + data[idx + 1].asInt32 && 0b111111 << 6 +
640 data[idx + 2].asInt32 && 0b111111
641 return Char32(result)
642 }
643 assert idx + 3 < _length
644 result := result && 0b111 << 18 + data[idx + 1].asInt32 && 0b111111 << 12 +
645 data[idx + 2].asInt32 && 0b111111 << 6 +
646 data[idx + 3].asInt32 && 0b111111
647 return Char32(result)
648 }
649
650 ================================================================================================
651 Returns the Unicode codepoint at the given offset within the string. This overload of the `[]`
652 operator is slower than the overload that accepts an `Index` parameter, as it must scan the
653 (internally UTF-8) string from the beginning to find the correct index.
654 ================================================================================================
655 function [](index:Int):Char32 {
656 return self[offset(start, index)]
657 }
658
659 function [](r:Range<Index>):String {
660 -- FIXME do this without a copy
661 return toString[Range<String.Index>(String.Index(r.min.byteOffset),
662 String.Index(r.max.byteOffset), r.inclusive)]
663 }
664
665 function [](r:Range<Index?>):String {
666 -- FIXME do this without a copy
667 def min:String.Index?
668 if r.min !== null {
669 min := String.Index(r.min.byteOffset)
670 }
671 else {
672 min := null
673 }
674 def max:String.Index?
675 if r.max !== null {
676 max := String.Index(r.max.byteOffset)
677 }
678 else {
679 max := null
680 }
681 return toString[Range<String.Index>(min, max, r.inclusive)]
682 }
683
684 function [](r:Range<Int>):String {
685 -- FIXME do this without a copy
686 return toString[r]
687 }
688
689 function [](r:Range<Int?>):String {
690 -- FIXME do this without a copy
691 return toString[r]
692 }
693
694 function [](r:SteppedRange<Index?, Int>):String {
695 -- FIXME do this without a copy
696 def start:String.Index?
697 if r.start !== null {
698 start := String.Index(r.start.byteOffset)
699 }
700 else {
701 start := null
702 }
703 def end:String.Index?
704 if r.end !== null {
705 end := String.Index(r.end.byteOffset)
706 }
707 else {
708 end := null
709 }
710 return toString[SteppedRange<String.Index?, Int>(start, end, r.step, r.inclusive)]
711 }
712
713 function [](r:SteppedRange<Int?, Int>):String {
714 -- FIXME do this without a copy
715 return toString[r]
716 }
717
718 -- FIXME @self
719 method []:=(index:Int, c:Char32) {
720 self[index ... index] := c.toString
721 }
722
723 -- FIXME @self
724 method []:=(index:Index, c:Char32) {
725 self[index ... index] := c.toString
726 }
727
728 -- FIXME @self
729 @pre(r.max >= r.min &
730 ((r.inclusive & r.min.byteOffset < _length &< _length & r.max.byteOffset < _length)< _length) |
731 (!r.inclusive & r.min.byteOffset <= _length & r.max.byteOffset <= _length)))
732 @unsafeAccess
733 method []:=(r:Range<Index>, s:String) {
734 var max := r.max.byteOffset
735 if r.inclusive {
736 max += 1
737 }
738 def rangeLength := max - r.min.byteOffset
739 def newLength := _length - rangeLength + s._length
740 ensureCapacity(newLength)
741 def offset := s._length - rangeLength
742 if s.byteLength > rangeLength {
743 for i in _length - 1 ... max by -1 {
744 data[i + offset] := data[i]
745 }
746 }
747 else {
748 for i in max .. _length {
749 data[i + offset] := data[i]
750 }
751 }
752 for i in 0 .. s._length {
753 data[r.min.byteOffset + i] := s.data[i]
754 }
755 _length := newLength
756 }
757
758 -- FIXME @self
759 method []:=(r:Range<Int>, s:String) {
760 self[Range<Index>(offset(start, r.min), offset(start, r.max), r.inclusive)] := s
761 }
762
763 -- FIXME @self
764 @priority(1)
765 method []:=(r:Range<Index?>, s:String) {
766 def min:Index
767 if r.min !== null {
768 min := r.min
769 }
770 else {
771 min := start
772 }
773 var inclusive := r.inclusive
774 def max:Index
775 if r.max !== null {
776 max := r.max
777 }
778 else {
779 max := end
780 inclusive := false
781 }
782 self[Range<Index>(min, max, inclusive)] := s
783 }
784
785 -- FIXME @self
786 method []:=(r:Range<Int?>, s:String) {
787 def min:Index
788 if r.min !== null {
789 min := offset(start, r.min)
790 }
791 else {
792 min := start
793 }
794 var inclusive := r.inclusive
795 def max:Index
796 if r.max !== null {
797 max := offset(start, r.max)
798 }
799 else {
800 max := end
801 inclusive := false
802 }
803 self[Range<Index>(min, max, inclusive)] := s
804 }
805
806 -- FIXME @self
807 method replace(search:String, replacement:String) {
808 var index := start
809 loop {
810 def next := indexOf(search, index)
811 if next == null {
812 break
813 }
814 self[next .. Index(next.byteOffset + search.byteLength)] := replacement
815 index := Index(next.byteOffset + replacement.byteLength.max(1))
816 }
817 }
818
819 @private
820 -- FIXME @self
821 @pre(maxLength > 0)
822 method ensureCapacity(newSize:Int) {
823 if maxLength >= newSize {
824 return
825 }
826 def oldMax := maxLength
827 while maxLength < newSize {< newSize {
828 maxLength *= 2
829 }
830 data := data.realloc(oldMax, maxLength)
831 }
832
833 -- FIXME @self
834 method clear() {
835 data := data.realloc(maxLength, DEFAULT_SIZE)
836 _length := 0
837 maxLength := DEFAULT_SIZE
838 }
839
840 ================================================================================================
841 Returns an immutable copy of this `MutableString`. Typically it is better to use [finish()] for
842 performance reasons, as that does not make a copy.
843 ================================================================================================
844 @override
845 function get_toString():String {
846 def result := Pointer<Char8>.alloc(_length)
847 for i in 0 .. _length {
848 result[i] := data[i]
849 }
850 return String(result, _length)
851 }
852
853 ================================================================================================
854 Invalidates this `MutableString` and returns its contents as an immutable `String`. This is
855 generally preferable to [toString], as it does not copy the string's contents. Interacting in
856 any way with a `MutableString` after `finish`ing will cause precondition violations (or, if
857 safety checks are disabled, undefined behavior).
858 ================================================================================================
859 -- FIXME @self
860 @unsafeAccess
861 method finish():String {
862 -- FIXME this transformation is only safe at -S0
863 data := data.realloc(maxLength, _length)
864 maxLength := -1
865 self.$class := "".$class
866 return self->Object->String
867 -- maxLength := -1
868 -- return String(data, length)
869 }
870 }