nitlanguage / nit.git / blob
? search:


13bf585ab001ef3fd859eb175b41edae01079b7e
[nit.git] / lib / standard / string.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
4 # Copyright 2006-2008 Floréal Morandat <morandat@lirmm.fr>
5 #
6 # This file is free software, which comes along with NIT. This software is
7 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
8 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
9 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
10 # is kept unaltered, and a notification of the changes is added.
11 # You are allowed to redistribute it and sell it, alone or is a part of
12 # another product.
13
14 # Basic manipulations of strings of characters
15 module string
16
17 import math
18 intrude import collection # FIXME should be collection::array
19
20 `{
21 #include <stdio.h>
22 #include <string.h>
23 `}
24
25 ###############################################################################
26 # String #
27 ###############################################################################
28
29 # High-level abstraction for all text representations
30 abstract class Text
31 super Comparable
32 super StringCapable
33
34 redef type OTHER: Text
35
36 # Type of self (used for factorization of several methods, ex : substring_from, empty...)
37 type SELFTYPE: Text
38
39 # Gets a view on the chars of the Text object
40 #
41 # assert "hello".chars.to_a == ['h', 'e', 'l', 'l', 'o']
42 fun chars: SequenceRead[Char] is abstract
43
44 # Number of characters contained in self.
45 #
46 # assert "12345".length == 5
47 # assert "".length == 0
48 fun length: Int is abstract
49
50 # Create a substring.
51 #
52 # assert "abcd".substring(1, 2) == "bc"
53 # assert "abcd".substring(-1, 2) == "a"
54 # assert "abcd".substring(1, 0) == ""
55 # assert "abcd".substring(2, 5) == "cd"
56 #
57 # A `from` index < 0 will be replaced by 0.
58 # Unless a `count` value is > 0 at the same time.
59 # In this case, `from += count` and `count -= from`.
60 fun substring(from: Int, count: Int): SELFTYPE is abstract
61
62 # Iterates on the substrings of self if any
63 fun substrings: Iterator[Text] is abstract
64
65 # Concatenates `o` to `self`
66 #
67 # assert "hello" + "world" == "helloworld"
68 # assert "" + "hello" + "" == "hello"
69 fun +(o: Text): SELFTYPE is abstract
70
71 # Auto-concatenates self `i` times
72 #
73 # assert "abc" * 4 == "abcabcabcabc"
74 # assert "abc" * 1 == "abc"
75 # assert "abc" * 0 == ""
76 fun *(i: Int): SELFTYPE is abstract
77
78 # Is the current Text empty (== "")
79 #
80 # assert "".is_empty
81 # assert not "foo".is_empty
82 fun is_empty: Bool do return self.length == 0
83
84 # Returns an empty Text of the right type
85 #
86 # This method is used internally to get the right
87 # implementation of an empty string.
88 protected fun empty: SELFTYPE is abstract
89
90 # Gets the first char of the Text
91 #
92 # DEPRECATED : Use self.chars.first instead
93 fun first: Char do return self.chars[0]
94
95 # Access a character at `index` in the string.
96 #
97 # assert "abcd"[2] == 'c'
98 #
99 # DEPRECATED : Use self.chars.[] instead
100 fun [](index: Int): Char do return self.chars[index]
101
102 # Gets the index of the first occurence of 'c'
103 #
104 # Returns -1 if not found
105 #
106 # DEPRECATED : Use self.chars.index_of instead
107 fun index_of(c: Char): Int
108 do
109 return index_of_from(c, 0)
110 end
111
112 # Gets the last char of self
113 #
114 # DEPRECATED : Use self.chars.last instead
115 fun last: Char do return self.chars[length-1]
116
117 # Gets the index of the first occurence of ´c´ starting from ´pos´
118 #
119 # Returns -1 if not found
120 #
121 # DEPRECATED : Use self.chars.index_of_from instead
122 fun index_of_from(c: Char, pos: Int): Int
123 do
124 var iter = self.chars.iterator_from(pos)
125 while iter.is_ok do
126 if iter.item == c then return iter.index
127 iter.next
128 end
129 return -1
130 end
131
132 # Gets the last index of char ´c´
133 #
134 # Returns -1 if not found
135 #
136 # DEPRECATED : Use self.chars.last_index_of instead
137 fun last_index_of(c: Char): Int
138 do
139 return last_index_of_from(c, length - 1)
140 end
141
142 # Return a null terminated char *
143 fun to_cstring: NativeString do return flatten.to_cstring
144
145 # The index of the last occurrence of an element starting from pos (in reverse order).
146 #
147 # var s = "/etc/bin/test/test.nit"
148 # assert s.last_index_of_from('/', s.length-1) == 13
149 # assert s.last_index_of_from('/', 12) == 8
150 #
151 # Returns -1 if not found
152 #
153 # DEPRECATED : Use self.chars.last_index_of_from instead
154 fun last_index_of_from(item: Char, pos: Int): Int
155 do
156 var iter = self.chars.reverse_iterator_from(pos)
157 while iter.is_ok do
158 if iter.item == item then return iter.index
159 iter.next
160 end
161 return -1
162 end
163
164 # Gets an iterator on the chars of self
165 #
166 # DEPRECATED : Use self.chars.iterator instead
167 fun iterator: Iterator[Char]
168 do
169 return self.chars.iterator
170 end
171
172 # Is 'c' contained in self ?
173 #
174 # DEPRECATED : Use self.chars.has instead
175 fun has(c: Char): Bool
176 do
177 return self.chars.has(c)
178 end
179
180 # Gets an Array containing the chars of self
181 #
182 # DEPRECATED : Use self.chars.to_a instead
183 fun to_a: Array[Char] do return chars.to_a
184
185 # Create a substring from `self` beginning at the `from` position
186 #
187 # assert "abcd".substring_from(1) == "bcd"
188 # assert "abcd".substring_from(-1) == "abcd"
189 # assert "abcd".substring_from(2) == "cd"
190 #
191 # As with substring, a `from` index < 0 will be replaced by 0
192 fun substring_from(from: Int): SELFTYPE
193 do
194 if from > self.length then return empty
195 if from < 0 then from = 0
196 return substring(from, length - from)
197 end
198
199 # Returns a reversed version of self
200 #
201 # assert "hello".reversed == "olleh"
202 # assert "bob".reversed == "bob"
203 # assert "".reversed == ""
204 fun reversed: SELFTYPE is abstract
205
206 # Does self have a substring `str` starting from position `pos`?
207 #
208 # assert "abcd".has_substring("bc",1) == true
209 # assert "abcd".has_substring("bc",2) == false
210 fun has_substring(str: String, pos: Int): Bool
211 do
212 var myiter = self.chars.iterator_from(pos)
213 var itsiter = str.chars.iterator
214 while myiter.is_ok and itsiter.is_ok do
215 if myiter.item != itsiter.item then return false
216 myiter.next
217 itsiter.next
218 end
219 if itsiter.is_ok then return false
220 return true
221 end
222
223 # Is this string prefixed by `prefix`?
224 #
225 # assert "abcd".has_prefix("ab") == true
226 # assert "abcbc".has_prefix("bc") == false
227 # assert "ab".has_prefix("abcd") == false
228 fun has_prefix(prefix: String): Bool do return has_substring(prefix,0)
229
230 # Is this string suffixed by `suffix`?
231 #
232 # assert "abcd".has_suffix("abc") == false
233 # assert "abcd".has_suffix("bcd") == true
234 fun has_suffix(suffix: String): Bool do return has_substring(suffix, length - suffix.length)
235
236 # If `self` contains only digits, return the corresponding integer
237 #
238 # assert "123".to_i == 123
239 # assert "-1".to_i == -1
240 fun to_i: Int
241 do
242 # Shortcut
243 return to_s.to_cstring.atoi
244 end
245
246 # If `self` contains a float, return the corresponding float
247 #
248 # assert "123".to_f == 123.0
249 # assert "-1".to_f == -1.0
250 # assert "-1.2e-3".to_f == -0.0012
251 fun to_f: Float
252 do
253 # Shortcut
254 return to_s.to_cstring.atof
255 end
256
257 # If `self` contains only digits and alpha <= 'f', return the corresponding integer.
258 #
259 # assert "ff".to_hex == 255
260 fun to_hex: Int do return a_to(16)
261
262 # If `self` contains only digits and letters, return the corresponding integer in a given base
263 #
264 # assert "120".a_to(3) == 15
265 fun a_to(base: Int) : Int
266 do
267 var i = 0
268 var neg = false
269
270 for c in self.chars
271 do
272 var v = c.to_i
273 if v > base then
274 if neg then
275 return -i
276 else
277 return i
278 end
279 else if v < 0 then
280 neg = true
281 else
282 i = i * base + v
283 end
284 end
285 if neg then
286 return -i
287 else
288 return i
289 end
290 end
291
292 # Returns `true` if the string contains only Numeric values (and one "," or one "." character)
293 #
294 # assert "123".is_numeric == true
295 # assert "1.2".is_numeric == true
296 # assert "1,2".is_numeric == true
297 # assert "1..2".is_numeric == false
298 fun is_numeric: Bool
299 do
300 var has_point_or_comma = false
301 for i in self.chars
302 do
303 if not i.is_numeric
304 then
305 if (i == '.' or i == ',') and not has_point_or_comma
306 then
307 has_point_or_comma = true
308 else
309 return false
310 end
311 end
312 end
313 return true
314 end
315
316 # A upper case version of `self`
317 #
318 # assert "Hello World!".to_upper == "HELLO WORLD!"
319 fun to_upper: SELFTYPE is abstract
320
321 # A lower case version of `self`
322 #
323 # assert "Hello World!".to_lower == "hello world!"
324 fun to_lower : SELFTYPE is abstract
325
326 # Removes the whitespaces at the beginning of self
327 #
328 # assert " \n\thello \n\t".l_trim == "hello \n\t"
329 #
330 # A whitespace is defined as any character which ascii value is less than or equal to 32
331 fun l_trim: SELFTYPE
332 do
333 var iter = self.chars.iterator
334 while iter.is_ok do
335 if iter.item.ascii > 32 then break
336 iter.next
337 end
338 if iter.index == length then return self.empty
339 return self.substring_from(iter.index)
340 end
341
342 # Removes the whitespaces at the end of self
343 #
344 # assert " \n\thello \n\t".r_trim == " \n\thello"
345 #
346 # A whitespace is defined as any character which ascii value is less than or equal to 32
347 fun r_trim: SELFTYPE
348 do
349 var iter = self.chars.reverse_iterator
350 while iter.is_ok do
351 if iter.item.ascii > 32 then break
352 iter.next
353 end
354 if iter.index == length then return self.empty
355 return self.substring(0, iter.index + 1)
356 end
357
358 # Trims trailing and preceding white spaces
359 # A whitespace is defined as any character which ascii value is less than or equal to 32
360 #
361 # assert " Hello World ! ".trim == "Hello World !"
362 # assert "\na\nb\tc\t".trim == "a\nb\tc"
363 fun trim: SELFTYPE do return (self.l_trim).r_trim
364
365 # Mangle a string to be a unique string only made of alphanumeric characters
366 fun to_cmangle: String
367 do
368 var res = new FlatBuffer
369 var underscore = false
370 for c in self.chars do
371 if (c >= 'a' and c <= 'z') or (c >='A' and c <= 'Z') then
372 res.add(c)
373 underscore = false
374 continue
375 end
376 if underscore then
377 res.append('_'.ascii.to_s)
378 res.add('d')
379 end
380 if c >= '0' and c <= '9' then
381 res.add(c)
382 underscore = false
383 else if c == '_' then
384 res.add(c)
385 underscore = true
386 else
387 res.add('_')
388 res.append(c.ascii.to_s)
389 res.add('d')
390 underscore = false
391 end
392 end
393 return res.to_s
394 end
395
396 # Escape " \ ' and non printable characters using the rules of literal C strings and characters
397 #
398 # assert "abAB12<>&".escape_to_c == "abAB12<>&"
399 # assert "\n\"'\\".escape_to_c == "\\n\\\"\\'\\\\"
400 fun escape_to_c: String
401 do
402 var b = new FlatBuffer
403 for c in self.chars do
404 if c == '\n' then
405 b.append("\\n")
406 else if c == '\0' then
407 b.append("\\0")
408 else if c == '"' then
409 b.append("\\\"")
410 else if c == '\'' then
411 b.append("\\\'")
412 else if c == '\\' then
413 b.append("\\\\")
414 else if c.ascii < 32 then
415 b.append("\\{c.ascii.to_base(8, false)}")
416 else
417 b.add(c)
418 end
419 end
420 return b.to_s
421 end
422
423 # Escape additionnal characters
424 # The result might no be legal in C but be used in other languages
425 #
426 # assert "ab|\{\}".escape_more_to_c("|\{\}") == "ab\\|\\\{\\\}"
427 fun escape_more_to_c(chars: String): String
428 do
429 var b = new FlatBuffer
430 for c in escape_to_c.chars do
431 if chars.chars.has(c) then
432 b.add('\\')
433 end
434 b.add(c)
435 end
436 return b.to_s
437 end
438
439 # Escape to C plus braces
440 #
441 # assert "\n\"'\\\{\}".escape_to_nit == "\\n\\\"\\'\\\\\\\{\\\}"
442 fun escape_to_nit: String do return escape_more_to_c("\{\}")
443
444 # Return a string where Nit escape sequences are transformed.
445 #
446 # var s = "\\n"
447 # assert s.length == 2
448 # var u = s.unescape_nit
449 # assert u.length == 1
450 # assert u.chars[0].ascii == 10 # (the ASCII value of the "new line" character)
451 fun unescape_nit: String
452 do
453 var res = new FlatBuffer.with_capacity(self.length)
454 var was_slash = false
455 for c in chars do
456 if not was_slash then
457 if c == '\\' then
458 was_slash = true
459 else
460 res.add(c)
461 end
462 continue
463 end
464 was_slash = false
465 if c == 'n' then
466 res.add('\n')
467 else if c == 'r' then
468 res.add('\r')
469 else if c == 't' then
470 res.add('\t')
471 else if c == '0' then
472 res.add('\0')
473 else
474 res.add(c)
475 end
476 end
477 return res.to_s
478 end
479
480 # Equality of text
481 # Two pieces of text are equals if thez have the same characters in the same order.
482 #
483 # assert "hello" == "hello"
484 # assert "hello" != "HELLO"
485 # assert "hello" == "hel"+"lo"
486 #
487 # Things that are not Text are not equal.
488 #
489 # assert "9" != '9'
490 # assert "9" != ['9']
491 # assert "9" != 9
492 #
493 # assert "9".chars.first == '9' # equality of Char
494 # assert "9".chars == ['9'] # equality of Sequence
495 # assert "9".to_i == 9 # equality of Int
496 redef fun ==(o)
497 do
498 if o == null then return false
499 if not o isa Text then return false
500 if self.is_same_instance(o) then return true
501 if self.length != o.length then return false
502 return self.chars == o.chars
503 end
504
505 # Lexicographical comparaison
506 #
507 # assert "abc" < "xy"
508 # assert "ABC" < "abc"
509 redef fun <(other)
510 do
511 var self_chars = self.chars.iterator
512 var other_chars = other.chars.iterator
513
514 while self_chars.is_ok and other_chars.is_ok do
515 if self_chars.item < other_chars.item then return true
516 if self_chars.item > other_chars.item then return false
517 self_chars.next
518 other_chars.next
519 end
520
521 if self_chars.is_ok then
522 return false
523 else
524 return true
525 end
526 end
527
528 # Flat representation of self
529 fun flatten: FlatText is abstract
530
531 private var hash_cache: nullable Int = null
532
533 redef fun hash
534 do
535 if hash_cache == null then
536 # djb2 hash algorithm
537 var h = 5381
538
539 for char in self.chars do
540 h = h.lshift(5) + h + char.ascii
541 end
542
543 hash_cache = h
544 end
545 return hash_cache.as(not null)
546 end
547
548 end
549
550 # All kinds of array-based text representations.
551 abstract class FlatText
552 super Text
553
554 private var items: NativeString
555
556 # Real items, used as cache for to_cstring is called
557 private var real_items: nullable NativeString = null
558
559 redef var length: Int = 0
560
561 init do end
562
563 redef fun output
564 do
565 var i = 0
566 while i < length do
567 items[i].output
568 i += 1
569 end
570 end
571
572 redef fun flatten do return self
573 end
574
575 # Abstract class for the SequenceRead compatible
576 # views on String and Buffer objects
577 private abstract class StringCharView
578 super SequenceRead[Char]
579
580 type SELFTYPE: Text
581
582 private var target: SELFTYPE
583
584 private init(tgt: SELFTYPE)
585 do
586 target = tgt
587 end
588
589 redef fun is_empty do return target.is_empty
590
591 redef fun length do return target.length
592
593 redef fun iterator: IndexedIterator[Char] do return self.iterator_from(0)
594
595 redef fun reverse_iterator do return self.reverse_iterator_from(self.length - 1)
596 end
597
598 # View on Buffer objects, extends Sequence
599 # for mutation operations
600 private abstract class BufferCharView
601 super StringCharView
602 super Sequence[Char]
603
604 redef type SELFTYPE: Buffer
605
606 end
607
608 abstract class String
609 super Text
610
611 redef type SELFTYPE: String
612
613 redef fun to_s do return self
614 end
615
616 private class FlatSubstringsIter
617 super Iterator[FlatText]
618
619 var tgt: nullable FlatText
620
621 init(tgt: FlatText) do self.tgt = tgt
622
623 redef fun item do
624 assert is_ok
625 return tgt.as(not null)
626 end
627
628 redef fun is_ok do return tgt != null
629
630 redef fun next do tgt = null
631 end
632
633 # Immutable strings of characters.
634 class FlatString
635 super FlatText
636 super String
637
638 # Index in _items of the start of the string
639 private var index_from: Int
640
641 # Indes in _items of the last item of the string
642 private var index_to: Int
643
644 redef var chars: SequenceRead[Char] = new FlatStringCharView(self)
645
646 ################################################
647 # AbstractString specific methods #
648 ################################################
649
650 redef fun reversed
651 do
652 var native = calloc_string(self.length + 1)
653 var length = self.length
654 var items = self.items
655 var pos = 0
656 var ipos = length-1
657 while pos < length do
658 native[pos] = items[ipos]
659 pos += 1
660 ipos -= 1
661 end
662 return native.to_s_with_length(self.length)
663 end
664
665 redef fun substring(from, count)
666 do
667 assert count >= 0
668
669 if from < 0 then
670 count += from
671 if count < 0 then count = 0
672 from = 0
673 end
674
675 var realFrom = index_from + from
676
677 if (realFrom + count) > index_to then return new FlatString.with_infos(items, index_to - realFrom + 1, realFrom, index_to)
678
679 if count == 0 then return empty
680
681 var to = realFrom + count - 1
682
683 return new FlatString.with_infos(items, to - realFrom + 1, realFrom, to)
684 end
685
686 redef fun empty do return "".as(FlatString)
687
688 redef fun to_upper
689 do
690 var outstr = calloc_string(self.length + 1)
691 var out_index = 0
692
693 var myitems = self.items
694 var index_from = self.index_from
695 var max = self.index_to
696
697 while index_from <= max do
698 outstr[out_index] = myitems[index_from].to_upper
699 out_index += 1
700 index_from += 1
701 end
702
703 outstr[self.length] = '\0'
704
705 return outstr.to_s_with_length(self.length)
706 end
707
708 redef fun to_lower
709 do
710 var outstr = calloc_string(self.length + 1)
711 var out_index = 0
712
713 var myitems = self.items
714 var index_from = self.index_from
715 var max = self.index_to
716
717 while index_from <= max do
718 outstr[out_index] = myitems[index_from].to_lower
719 out_index += 1
720 index_from += 1
721 end
722
723 outstr[self.length] = '\0'
724
725 return outstr.to_s_with_length(self.length)
726 end
727
728 redef fun output
729 do
730 var i = self.index_from
731 var imax = self.index_to
732 while i <= imax do
733 items[i].output
734 i += 1
735 end
736 end
737
738 ##################################################
739 # String Specific Methods #
740 ##################################################
741
742 private init with_infos(items: NativeString, len: Int, from: Int, to: Int)
743 do
744 self.items = items
745 length = len
746 index_from = from
747 index_to = to
748 end
749
750 redef fun to_cstring: NativeString
751 do
752 if real_items != null then return real_items.as(not null)
753 if index_from > 0 or index_to != items.cstring_length - 1 then
754 var newItems = calloc_string(length + 1)
755 self.items.copy_to(newItems, length, index_from, 0)
756 newItems[length] = '\0'
757 self.real_items = newItems
758 return newItems
759 end
760 return items
761 end
762
763 redef fun ==(other)
764 do
765 if not other isa FlatString then return super
766
767 if self.object_id == other.object_id then return true
768
769 var my_length = length
770
771 if other.length != my_length then return false
772
773 var my_index = index_from
774 var its_index = other.index_from
775
776 var last_iteration = my_index + my_length
777
778 var itsitems = other.items
779 var myitems = self.items
780
781 while my_index < last_iteration do
782 if myitems[my_index] != itsitems[its_index] then return false
783 my_index += 1
784 its_index += 1
785 end
786
787 return true
788 end
789
790 redef fun <(other)
791 do
792 if not other isa FlatString then return super
793
794 if self.object_id == other.object_id then return false
795
796 var my_curr_char : Char
797 var its_curr_char : Char
798
799 var curr_id_self = self.index_from
800 var curr_id_other = other.index_from
801
802 var my_items = self.items
803 var its_items = other.items
804
805 var my_length = self.length
806 var its_length = other.length
807
808 var max_iterations = curr_id_self + my_length
809
810 while curr_id_self < max_iterations do
811 my_curr_char = my_items[curr_id_self]
812 its_curr_char = its_items[curr_id_other]
813
814 if my_curr_char != its_curr_char then
815 if my_curr_char < its_curr_char then return true
816 return false
817 end
818
819 curr_id_self += 1
820 curr_id_other += 1
821 end
822
823 return my_length < its_length
824 end
825
826 redef fun +(s)
827 do
828 var my_length = self.length
829 var its_length = s.length
830
831 var total_length = my_length + its_length
832
833 var target_string = calloc_string(my_length + its_length + 1)
834
835 self.items.copy_to(target_string, my_length, index_from, 0)
836 if s isa FlatString then
837 s.items.copy_to(target_string, its_length, s.index_from, my_length)
838 else if s isa FlatBuffer then
839 s.items.copy_to(target_string, its_length, 0, my_length)
840 else
841 var curr_pos = my_length
842 for i in s.chars do
843 target_string[curr_pos] = i
844 curr_pos += 1
845 end
846 end
847
848 target_string[total_length] = '\0'
849
850 return target_string.to_s_with_length(total_length)
851 end
852
853 redef fun *(i)
854 do
855 assert i >= 0
856
857 var my_length = self.length
858
859 var final_length = my_length * i
860
861 var my_items = self.items
862
863 var target_string = calloc_string((final_length) + 1)
864
865 target_string[final_length] = '\0'
866
867 var current_last = 0
868
869 for iteration in [1 .. i] do
870 my_items.copy_to(target_string, my_length, 0, current_last)
871 current_last += my_length
872 end
873
874 return target_string.to_s_with_length(final_length)
875 end
876
877 redef fun hash
878 do
879 if hash_cache == null then
880 # djb2 hash algorithm
881 var h = 5381
882 var i = index_from
883
884 var myitems = items
885
886 while i <= index_to do
887 h = h.lshift(5) + h + myitems[i].ascii
888 i += 1
889 end
890
891 hash_cache = h
892 end
893
894 return hash_cache.as(not null)
895 end
896
897 redef fun substrings do return new FlatSubstringsIter(self)
898 end
899
900 private class FlatStringReverseIterator
901 super IndexedIterator[Char]
902
903 var target: FlatString
904
905 var target_items: NativeString
906
907 var curr_pos: Int
908
909 init with_pos(tgt: FlatString, pos: Int)
910 do
911 target = tgt
912 target_items = tgt.items
913 curr_pos = pos + tgt.index_from
914 end
915
916 redef fun is_ok do return curr_pos >= 0
917
918 redef fun item do return target_items[curr_pos]
919
920 redef fun next do curr_pos -= 1
921
922 redef fun index do return curr_pos - target.index_from
923
924 end
925
926 private class FlatStringIterator
927 super IndexedIterator[Char]
928
929 var target: FlatString
930
931 var target_items: NativeString
932
933 var curr_pos: Int
934
935 init with_pos(tgt: FlatString, pos: Int)
936 do
937 target = tgt
938 target_items = tgt.items
939 curr_pos = pos + target.index_from
940 end
941
942 redef fun is_ok do return curr_pos <= target.index_to
943
944 redef fun item do return target_items[curr_pos]
945
946 redef fun next do curr_pos += 1
947
948 redef fun index do return curr_pos - target.index_from
949
950 end
951
952 private class FlatStringCharView
953 super StringCharView
954
955 redef type SELFTYPE: FlatString
956
957 redef fun [](index)
958 do
959 # Check that the index (+ index_from) is not larger than indexTo
960 # In other terms, if the index is valid
961 assert index >= 0
962 var target = self.target
963 assert (index + target.index_from) <= target.index_to
964 return target.items[index + target.index_from]
965 end
966
967 redef fun iterator_from(start) do return new FlatStringIterator.with_pos(target, start)
968
969 redef fun reverse_iterator_from(start) do return new FlatStringReverseIterator.with_pos(target, start)
970
971 end
972
973 abstract class Buffer
974 super Text
975
976 redef type SELFTYPE: Buffer
977
978 # Specific implementations MUST set this to `true` in order to invalidate caches
979 protected var is_dirty = true
980
981 # Modifies the char contained at pos `index`
982 #
983 # DEPRECATED : Use self.chars.[]= instead
984 fun []=(index: Int, item: Char) is abstract
985
986 # Adds a char `c` at the end of self
987 #
988 # DEPRECATED : Use self.chars.add instead
989 fun add(c: Char) is abstract
990
991 # Clears the buffer
992 #
993 # var b = new FlatBuffer
994 # b.append "hello"
995 # assert not b.is_empty
996 # b.clear
997 # assert b.is_empty
998 fun clear is abstract
999
1000 # Enlarges the subsequent array containing the chars of self
1001 fun enlarge(cap: Int) is abstract
1002
1003 # Adds the content of text `s` at the end of self
1004 #
1005 # var b = new FlatBuffer
1006 # b.append "hello"
1007 # b.append "world"
1008 # assert b == "helloworld"
1009 fun append(s: Text) is abstract
1010
1011 redef fun hash
1012 do
1013 if is_dirty then hash_cache = null
1014 return super
1015 end
1016
1017 # In Buffers, the internal sequence of character is mutable
1018 # Thus, `chars` can be used to modify the buffer.
1019 redef fun chars: Sequence[Char] is abstract
1020 end
1021
1022 # Mutable strings of characters.
1023 class FlatBuffer
1024 super FlatText
1025 super Buffer
1026
1027 redef type SELFTYPE: FlatBuffer
1028
1029 redef var chars: Sequence[Char] = new FlatBufferCharView(self)
1030
1031 private var capacity: Int = 0
1032
1033 redef fun substrings do return new FlatSubstringsIter(self)
1034
1035 redef fun []=(index, item)
1036 do
1037 is_dirty = true
1038 if index == length then
1039 add(item)
1040 return
1041 end
1042 assert index >= 0 and index < length
1043 items[index] = item
1044 end
1045
1046 redef fun add(c)
1047 do
1048 is_dirty = true
1049 if capacity <= length then enlarge(length + 5)
1050 items[length] = c
1051 length += 1
1052 end
1053
1054 redef fun clear do
1055 is_dirty = true
1056 length = 0
1057 end
1058
1059 redef fun empty do return new FlatBuffer
1060
1061 redef fun enlarge(cap)
1062 do
1063 var c = capacity
1064 if cap <= c then return
1065 while c <= cap do c = c * 2 + 2
1066 var a = calloc_string(c+1)
1067 if length > 0 then items.copy_to(a, length, 0, 0)
1068 items = a
1069 capacity = c
1070 end
1071
1072 redef fun to_s: String
1073 do
1074 return to_cstring.to_s_with_length(length)
1075 end
1076
1077 redef fun to_cstring
1078 do
1079 if is_dirty then
1080 var new_native = calloc_string(length + 1)
1081 new_native[length] = '\0'
1082 if length > 0 then items.copy_to(new_native, length, 0, 0)
1083 real_items = new_native
1084 is_dirty = false
1085 end
1086 return real_items.as(not null)
1087 end
1088
1089 # Create a new empty string.
1090 init do end
1091
1092 init from(s: Text)
1093 do
1094 capacity = s.length + 1
1095 length = s.length
1096 items = calloc_string(capacity)
1097 if s isa FlatString then
1098 s.items.copy_to(items, length, s.index_from, 0)
1099 else if s isa FlatBuffer then
1100 s.items.copy_to(items, length, 0, 0)
1101 else
1102 var curr_pos = 0
1103 for i in s.chars do
1104 items[curr_pos] = i
1105 curr_pos += 1
1106 end
1107 end
1108 end
1109
1110 # Create a new empty string with a given capacity.
1111 init with_capacity(cap: Int)
1112 do
1113 assert cap >= 0
1114 # _items = new NativeString.calloc(cap)
1115 items = calloc_string(cap+1)
1116 capacity = cap
1117 length = 0
1118 end
1119
1120 redef fun append(s)
1121 do
1122 if s.is_empty then return
1123 is_dirty = true
1124 var sl = s.length
1125 if capacity < length + sl then enlarge(length + sl)
1126 if s isa FlatString then
1127 s.items.copy_to(items, sl, s.index_from, length)
1128 else if s isa FlatBuffer then
1129 s.items.copy_to(items, sl, 0, length)
1130 else
1131 var curr_pos = self.length
1132 for i in s.chars do
1133 items[curr_pos] = i
1134 curr_pos += 1
1135 end
1136 end
1137 length += sl
1138 end
1139
1140 # Copies the content of self in `dest`
1141 fun copy(start: Int, len: Int, dest: Buffer, new_start: Int)
1142 do
1143 var self_chars = self.chars
1144 var dest_chars = dest.chars
1145 for i in [0..len-1] do
1146 dest_chars[new_start+i] = self_chars[start+i]
1147 end
1148 end
1149
1150 redef fun substring(from, count)
1151 do
1152 assert count >= 0
1153 count += from
1154 if from < 0 then from = 0
1155 if count > length then count = length
1156 if from < count then
1157 var r = new FlatBuffer.with_capacity(count - from)
1158 while from < count do
1159 r.chars.push(items[from])
1160 from += 1
1161 end
1162 return r
1163 else
1164 return new FlatBuffer
1165 end
1166 end
1167
1168 redef fun reversed
1169 do
1170 var new_buf = new FlatBuffer.with_capacity(self.length)
1171 var reviter = self.chars.reverse_iterator
1172 while reviter.is_ok do
1173 new_buf.add(reviter.item)
1174 reviter.next
1175 end
1176 return new_buf
1177 end
1178
1179 redef fun +(other)
1180 do
1181 var new_buf = new FlatBuffer.with_capacity(self.length + other.length)
1182 new_buf.append(self)
1183 new_buf.append(other)
1184 return new_buf
1185 end
1186
1187 redef fun *(repeats)
1188 do
1189 var new_buf = new FlatBuffer.with_capacity(self.length * repeats)
1190 for i in [0..repeats[ do
1191 new_buf.append(self)
1192 end
1193 return new_buf
1194 end
1195
1196 redef fun to_upper
1197 do
1198 var new_buf = new FlatBuffer.with_capacity(self.length)
1199 for i in self.chars do
1200 new_buf.add(i.to_upper)
1201 end
1202 return new_buf
1203 end
1204
1205 redef fun to_lower
1206 do
1207 var new_buf = new FlatBuffer.with_capacity(self.length)
1208 for i in self.chars do
1209 new_buf.add(i.to_lower)
1210 end
1211 return new_buf
1212 end
1213 end
1214
1215 private class FlatBufferReverseIterator
1216 super IndexedIterator[Char]
1217
1218 var target: FlatBuffer
1219
1220 var target_items: NativeString
1221
1222 var curr_pos: Int
1223
1224 init with_pos(tgt: FlatBuffer, pos: Int)
1225 do
1226 target = tgt
1227 if tgt.length > 0 then target_items = tgt.items
1228 curr_pos = pos
1229 end
1230
1231 redef fun index do return curr_pos
1232
1233 redef fun is_ok do return curr_pos >= 0
1234
1235 redef fun item do return target_items[curr_pos]
1236
1237 redef fun next do curr_pos -= 1
1238
1239 end
1240
1241 private class FlatBufferCharView
1242 super BufferCharView
1243 super StringCapable
1244
1245 redef type SELFTYPE: FlatBuffer
1246
1247 redef fun [](index) do return target.items[index]
1248
1249 redef fun []=(index, item)
1250 do
1251 assert index >= 0 and index <= length
1252 if index == length then
1253 add(item)
1254 return
1255 end
1256 target.items[index] = item
1257 end
1258
1259 redef fun push(c)
1260 do
1261 target.add(c)
1262 end
1263
1264 redef fun add(c)
1265 do
1266 target.add(c)
1267 end
1268
1269 fun enlarge(cap: Int)
1270 do
1271 target.enlarge(cap)
1272 end
1273
1274 redef fun append(s)
1275 do
1276 var my_items = target.items
1277 var s_length = s.length
1278 if target.capacity < s.length then enlarge(s_length + target.length)
1279 end
1280
1281 redef fun iterator_from(pos) do return new FlatBufferIterator.with_pos(target, pos)
1282
1283 redef fun reverse_iterator_from(pos) do return new FlatBufferReverseIterator.with_pos(target, pos)
1284
1285 end
1286
1287 private class FlatBufferIterator
1288 super IndexedIterator[Char]
1289
1290 var target: FlatBuffer
1291
1292 var target_items: NativeString
1293
1294 var curr_pos: Int
1295
1296 init with_pos(tgt: FlatBuffer, pos: Int)
1297 do
1298 target = tgt
1299 if tgt.length > 0 then target_items = tgt.items
1300 curr_pos = pos
1301 end
1302
1303 redef fun index do return curr_pos
1304
1305 redef fun is_ok do return curr_pos < target.length
1306
1307 redef fun item do return target_items[curr_pos]
1308
1309 redef fun next do curr_pos += 1
1310
1311 end
1312
1313 ###############################################################################
1314 # Refinement #
1315 ###############################################################################
1316
1317 redef class Object
1318 # User readable representation of `self`.
1319 fun to_s: String do return inspect
1320
1321 # The class name of the object in NativeString format.
1322 private fun native_class_name: NativeString is intern
1323
1324 # The class name of the object.
1325 #
1326 # assert 5.class_name == "Int"
1327 fun class_name: String do return native_class_name.to_s
1328
1329 # Developer readable representation of `self`.
1330 # Usually, it uses the form "<CLASSNAME:#OBJECTID bla bla bla>"
1331 fun inspect: String
1332 do
1333 return "<{inspect_head}>"
1334 end
1335
1336 # Return "CLASSNAME:#OBJECTID".
1337 # This function is mainly used with the redefinition of the inspect method
1338 protected fun inspect_head: String
1339 do
1340 return "{class_name}:#{object_id.to_hex}"
1341 end
1342
1343 protected fun args: Sequence[String]
1344 do
1345 return sys.args
1346 end
1347 end
1348
1349 redef class Bool
1350 # assert true.to_s == "true"
1351 # assert false.to_s == "false"
1352 redef fun to_s
1353 do
1354 if self then
1355 return once "true"
1356 else
1357 return once "false"
1358 end
1359 end
1360 end
1361
1362 redef class Int
1363
1364 # Wrapper of strerror C function
1365 private fun strerror_ext: NativeString is extern `{
1366 return strerror(recv);
1367 `}
1368
1369 # Returns a string describing error number
1370 fun strerror: String do return strerror_ext.to_s
1371
1372 # Fill `s` with the digits in base `base` of `self` (and with the '-' sign if 'signed' and negative).
1373 # assume < to_c max const of char
1374 private fun fill_buffer(s: Buffer, base: Int, signed: Bool)
1375 do
1376 var n: Int
1377 # Sign
1378 if self < 0 then
1379 n = - self
1380 s.chars[0] = '-'
1381 else if self == 0 then
1382 s.chars[0] = '0'
1383 return
1384 else
1385 n = self
1386 end
1387 # Fill digits
1388 var pos = digit_count(base) - 1
1389 while pos >= 0 and n > 0 do
1390 s.chars[pos] = (n % base).to_c
1391 n = n / base # /
1392 pos -= 1
1393 end
1394 end
1395
1396 # C function to convert an nit Int to a NativeString (char*)
1397 private fun native_int_to_s(len: Int): NativeString is extern "native_int_to_s"
1398
1399 # return displayable int in base 10 and signed
1400 #
1401 # assert 1.to_s == "1"
1402 # assert (-123).to_s == "-123"
1403 redef fun to_s do
1404 var len = digit_count(10)
1405 return native_int_to_s(len).to_s_with_length(len)
1406 end
1407
1408 # return displayable int in hexadecimal
1409 #
1410 # assert 1.to_hex == "1"
1411 # assert (-255).to_hex == "-ff"
1412 fun to_hex: String do return to_base(16,false)
1413
1414 # return displayable int in base base and signed
1415 fun to_base(base: Int, signed: Bool): String
1416 do
1417 var l = digit_count(base)
1418 var s = new FlatBuffer.from(" " * l)
1419 fill_buffer(s, base, signed)
1420 return s.to_s
1421 end
1422 end
1423
1424 redef class Float
1425 # Pretty print self, print needoed decimals up to a max of 3.
1426 #
1427 # assert 12.34.to_s == "12.34"
1428 # assert (-0120.03450).to_s == "-120.035"
1429 #
1430 # see `to_precision` for a different precision.
1431 redef fun to_s do
1432 var str = to_precision( 3 )
1433 if is_inf != 0 or is_nan then return str
1434 var len = str.length
1435 for i in [0..len-1] do
1436 var j = len-1-i
1437 var c = str.chars[j]
1438 if c == '0' then
1439 continue
1440 else if c == '.' then
1441 return str.substring( 0, j+2 )
1442 else
1443 return str.substring( 0, j+1 )
1444 end
1445 end
1446 return str
1447 end
1448
1449 # `self` representation with `nb` digits after the '.'.
1450 #
1451 # assert 12.345.to_precision(1) == "12.3"
1452 # assert 12.345.to_precision(2) == "12.35"
1453 # assert 12.345.to_precision(3) == "12.345"
1454 # assert 12.345.to_precision(4) == "12.3450"
1455 fun to_precision(nb: Int): String
1456 do
1457 if is_nan then return "nan"
1458
1459 var isinf = self.is_inf
1460 if isinf == 1 then
1461 return "inf"
1462 else if isinf == -1 then
1463 return "-inf"
1464 end
1465
1466 if nb == 0 then return self.to_i.to_s
1467 var f = self
1468 for i in [0..nb[ do f = f * 10.0
1469 if self > 0.0 then
1470 f = f + 0.5
1471 else
1472 f = f - 0.5
1473 end
1474 var i = f.to_i
1475 if i == 0 then return "0.0"
1476 var s = i.to_s
1477 var sl = s.length
1478 if sl > nb then
1479 var p1 = s.substring(0, s.length-nb)
1480 var p2 = s.substring(s.length-nb, nb)
1481 return p1 + "." + p2
1482 else
1483 return "0." + ("0"*(nb-sl)) + s
1484 end
1485 end
1486
1487 # `self` representation with `nb` digits after the '.'.
1488 #
1489 # assert 12.345.to_precision_native(1) == "12.3"
1490 # assert 12.345.to_precision_native(2) == "12.35"
1491 # assert 12.345.to_precision_native(3) == "12.345"
1492 # assert 12.345.to_precision_native(4) == "12.3450"
1493 fun to_precision_native(nb: Int): String import NativeString.to_s `{
1494 int size;
1495 char *str;
1496
1497 size = snprintf(NULL, 0, "%.*f", (int)nb, recv);
1498 str = malloc(size + 1);
1499 sprintf(str, "%.*f", (int)nb, recv );
1500
1501 return NativeString_to_s( str );
1502 `}
1503 end
1504
1505 redef class Char
1506 # assert 'x'.to_s == "x"
1507 redef fun to_s
1508 do
1509 var s = new FlatBuffer.with_capacity(1)
1510 s.chars[0] = self
1511 return s.to_s
1512 end
1513
1514 # Returns true if the char is a numerical digit
1515 #
1516 # assert '0'.is_numeric
1517 # assert '9'.is_numeric
1518 # assert not 'a'.is_numeric
1519 # assert not '?'.is_numeric
1520 fun is_numeric: Bool
1521 do
1522 return self >= '0' and self <= '9'
1523 end
1524
1525 # Returns true if the char is an alpha digit
1526 #
1527 # assert 'a'.is_alpha
1528 # assert 'Z'.is_alpha
1529 # assert not '0'.is_alpha
1530 # assert not '?'.is_alpha
1531 fun is_alpha: Bool
1532 do
1533 return (self >= 'a' and self <= 'z') or (self >= 'A' and self <= 'Z')
1534 end
1535
1536 # Returns true if the char is an alpha or a numeric digit
1537 #
1538 # assert 'a'.is_alphanumeric
1539 # assert 'Z'.is_alphanumeric
1540 # assert '0'.is_alphanumeric
1541 # assert '9'.is_alphanumeric
1542 # assert not '?'.is_alphanumeric
1543 fun is_alphanumeric: Bool
1544 do
1545 return self.is_numeric or self.is_alpha
1546 end
1547 end
1548
1549 redef class Collection[E]
1550 # Concatenate elements.
1551 redef fun to_s
1552 do
1553 var s = new FlatBuffer
1554 for e in self do if e != null then s.append(e.to_s)
1555 return s.to_s
1556 end
1557
1558 # Concatenate and separate each elements with `sep`.
1559 #
1560 # assert [1, 2, 3].join(":") == "1:2:3"
1561 # assert [1..3].join(":") == "1:2:3"
1562 fun join(sep: Text): String
1563 do
1564 if is_empty then return ""
1565
1566 var s = new FlatBuffer # Result
1567
1568 # Concat first item
1569 var i = iterator
1570 var e = i.item
1571 if e != null then s.append(e.to_s)
1572
1573 # Concat other items
1574 i.next
1575 while i.is_ok do
1576 s.append(sep)
1577 e = i.item
1578 if e != null then s.append(e.to_s)
1579 i.next
1580 end
1581 return s.to_s
1582 end
1583 end
1584
1585 redef class Array[E]
1586 # Fast implementation
1587 redef fun to_s
1588 do
1589 var s = new FlatBuffer
1590 var i = 0
1591 var l = length
1592 while i < l do
1593 var e = self[i]
1594 if e != null then s.append(e.to_s)
1595 i += 1
1596 end
1597 return s.to_s
1598 end
1599 end
1600
1601 redef class Map[K,V]
1602 # Concatenate couple of 'key value'.
1603 # key and value are separated by `couple_sep`.
1604 # each couple is separated each couple with `sep`.
1605 #
1606 # var m = new ArrayMap[Int, String]
1607 # m[1] = "one"
1608 # m[10] = "ten"
1609 # assert m.join("; ", "=") == "1=one; 10=ten"
1610 fun join(sep: String, couple_sep: String): String
1611 do
1612 if is_empty then return ""
1613
1614 var s = new FlatBuffer # Result
1615
1616 # Concat first item
1617 var i = iterator
1618 var k = i.key
1619 var e = i.item
1620 s.append("{k}{couple_sep}{e or else "<null>"}")
1621
1622 # Concat other items
1623 i.next
1624 while i.is_ok do
1625 s.append(sep)
1626 k = i.key
1627 e = i.item
1628 s.append("{k}{couple_sep}{e or else "<null>"}")
1629 i.next
1630 end
1631 return s.to_s
1632 end
1633 end
1634
1635 ###############################################################################
1636 # Native classes #
1637 ###############################################################################
1638
1639 # Native strings are simple C char *
1640 class NativeString
1641 super StringCapable
1642
1643 fun [](index: Int): Char is intern
1644 fun []=(index: Int, item: Char) is intern
1645 fun copy_to(dest: NativeString, length: Int, from: Int, to: Int) is intern
1646
1647 # Position of the first nul character.
1648 fun cstring_length: Int
1649 do
1650 var l = 0
1651 while self[l] != '\0' do l += 1
1652 return l
1653 end
1654 fun atoi: Int is intern
1655 fun atof: Float is extern "atof"
1656
1657 redef fun to_s
1658 do
1659 return to_s_with_length(cstring_length)
1660 end
1661
1662 fun to_s_with_length(length: Int): FlatString
1663 do
1664 assert length >= 0
1665 return new FlatString.with_infos(self, length, 0, length - 1)
1666 end
1667
1668 fun to_s_with_copy: FlatString
1669 do
1670 var length = cstring_length
1671 var new_self = calloc_string(length + 1)
1672 copy_to(new_self, length, 0, 0)
1673 return new FlatString.with_infos(new_self, length, 0, length - 1)
1674 end
1675
1676 end
1677
1678 # StringCapable objects can create native strings
1679 interface StringCapable
1680 protected fun calloc_string(size: Int): NativeString is intern
1681 end
1682
1683 redef class Sys
1684 var _args_cache: nullable Sequence[String]
1685
1686 redef fun args: Sequence[String]
1687 do
1688 if _args_cache == null then init_args
1689 return _args_cache.as(not null)
1690 end
1691
1692 # The name of the program as given by the OS
1693 fun program_name: String
1694 do
1695 return native_argv(0).to_s
1696 end
1697
1698 # Initialize `args` with the contents of `native_argc` and `native_argv`.
1699 private fun init_args
1700 do
1701 var argc = native_argc
1702 var args = new Array[String].with_capacity(0)
1703 var i = 1
1704 while i < argc do
1705 args[i-1] = native_argv(i).to_s
1706 i += 1
1707 end
1708 _args_cache = args
1709 end
1710
1711 # First argument of the main C function.
1712 private fun native_argc: Int is intern
1713
1714 # Second argument of the main C function.
1715 private fun native_argv(i: Int): NativeString is intern
1716 end
1717
1718 # Comparator that efficienlty use `to_s` to compare things
1719 #
1720 # The comparaison call `to_s` on object and use the result to order things.
1721 #
1722 # var a = [1, 2, 3, 10, 20]
1723 # (new CachedAlphaComparator).sort(a)
1724 # assert a == [1, 10, 2, 20, 3]
1725 #
1726 # Internally the result of `to_s` is cached in a HashMap to counter
1727 # uneficient implementation of `to_s`.
1728 #
1729 # Note: it caching is not usefull, see `alpha_comparator`
1730 class CachedAlphaComparator
1731 super Comparator[Object]
1732
1733 private var cache = new HashMap[Object, String]
1734
1735 private fun do_to_s(a: Object): String do
1736 if cache.has_key(a) then return cache[a]
1737 var res = a.to_s
1738 cache[a] = res
1739 return res
1740 end
1741
1742 redef fun compare(a, b) do
1743 return do_to_s(a) <=> do_to_s(b)
1744 end
1745 end
1746
1747 # see `alpha_comparator`
1748 private class AlphaComparator
1749 super Comparator[Object]
1750 redef fun compare(a, b) do return a.to_s <=> b.to_s
1751 end
1752
1753 # Stateless comparator that naively use `to_s` to compare things.
1754 #
1755 # Note: the result of `to_s` is not cached, thus can be invoked a lot
1756 # on a single instace. See `CachedAlphaComparator` as an alternative.
1757 #
1758 # var a = [1, 2, 3, 10, 20]
1759 # alpha_comparator.sort(a)
1760 # assert a == [1, 10, 2, 20, 3]
1761 fun alpha_comparator: Comparator[Object] do return once new AlphaComparator
Nit language project; an oo programing language and its tool suite.