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 package string
  16
  17 intrude import collection # FIXME should be collection::array
  18 import hash
  19
  20 ###############################################################################
  21 # String                                                                      #
  22 ###############################################################################
  23
  24 # Common subclass for String and Buffer
  25 abstract class AbstractString
  26         super AbstractArrayRead[Char]
  27
  28         readable private var _items: NativeString
  29
  30         redef fun [](index) do return _items[index]
  31
  32         # Create a substring.
  33         #
  34         # "abcd".substring(1, 2)        # --> "bc"
  35         # "abcd".substring(-1, 2)       # --> "a"
  36         # "abcd".substring(1, 0)     # --> ""
  37         # "abcd".substring(2, 5)     # --> "cd"
  38         fun substring(from: Int, count: Int): String
  39         do
  40                 assert count >= 0
  41                 count += from
  42                 if from < 0 then from = 0
  43                 if count > length then count = length
  44                 if from < count then
  45                         var r = new Buffer.with_capacity(count - from)
  46                         while from < count do
  47                                 r.push(_items[from])
  48                                 from += 1
  49                         end
  50                         return r.to_s
  51                 else
  52                         return ""
  53                 end
  54         end
  55
  56         # Create a substring from `self' beginning at the 'from' position
  57         #
  58         # "abcd".substring(1)   # --> "bcd"
  59         # "abcd".substring(-1)  # --> "abcd"
  60         # "abcd".substring(2)     # --> "cd"
  61         fun substring_from(from: Int): String
  62         do
  63                 assert from < length
  64                 return substring(from, length - from)
  65         end
  66
  67         # Is `self' a substring of the `str' string from pos `pos'
  68         #
  69         # "bc".is_substring("abcd",1)   # --> true
  70         # "bc".is_substring("abcd",2)   # --> false
  71         fun has_substring(str: String, pos: Int): Bool
  72         do
  73                 var itsindex = str.length - 1
  74                 var myindex = pos + itsindex
  75                 var myitems = _items
  76                 var itsitems = str._items
  77                 if myindex > length or itsindex > myindex  then return false
  78                 while itsindex >= 0 do
  79                         if myitems[myindex] != itsitems[itsindex] then return false
  80                         myindex -= 1
  81                         itsindex -= 1
  82                 end
  83                 return true
  84         end
  85
  86         # Is this string prefixed by 'prefix'
  87         #
  88         # "abc".is_prefix("abcd")       # --> true
  89         # "bc".is_prefix("abcd")        # --> false
  90         fun has_prefix(prefix: String): Bool do return has_substring(prefix,0)
  91
  92         # Is this string suffixed by 'suffix'
  93         #
  94         # "abcd".has_suffix("abc")      # --> false
  95         # "abcd".has_suffix("bcd")      # --> true
  96         fun has_suffix(suffix: String): Bool do return has_substring(suffix, length - suffix.length)
  97
  98         # If `self' contains only digits, return the corresponding integer
  99         fun to_i: Int
 100         do
 101                 # Shortcut
 102                 return to_s.to_cstring.atoi
 103         end
 104
 105         # If `self' contains a float, return the corresponding float
 106         fun to_f: Float
 107         do
 108                 # Shortcut
 109                 return to_s.to_cstring.atof
 110         end
 111
 112         # If `self' contains only digits and alpha <= 'f', return the corresponding integer.
 113         fun to_hex: Int do return a_to(16)
 114
 115         # If `self' contains only digits and letters, return the corresponding integer in a given base
 116         fun a_to(base: Int) : Int
 117         do
 118                 var i = 0
 119                 var neg = false
 120
 121                 for c in self
 122                 do
 123                         var v = c.to_i
 124                         if v > base then
 125                                 if neg then
 126                                         return -i
 127                                 else
 128                                         return i
 129                                 end
 130                         else if v < 0 then
 131                                 neg = true
 132                         else
 133                                 i = i * base + v
 134                         end
 135                 end
 136                 if neg then
 137                         return -i
 138                 else
 139                         return i
 140                 end
 141         end
 142
 143         # A upper case version of `self'
 144         fun to_upper: String
 145         do
 146                 var s = new Buffer.with_capacity(length)
 147                 for i in self do s.add(i.to_upper)
 148                 return s.to_s
 149         end
 150
 151         # A lower case version of `self'
 152         fun to_lower : String
 153         do
 154                 var s = new Buffer.with_capacity(length)
 155                 for i in self do s.add(i.to_lower)
 156                 return s.to_s
 157         end
 158
 159
 160         redef fun output
 161         do
 162                 var i = 0
 163                 while i < length do
 164                         _items[i].output
 165                         i += 1
 166                 end
 167         end
 168 end
 169
 170 # Immutable strings of characters.
 171 class String
 172         super Comparable
 173         super AbstractString
 174
 175         redef type OTHER: String
 176
 177         # Create a new string from a given char *.
 178         init with_native(nat: NativeString, size: Int)
 179         do
 180                 assert size >= 0
 181                 _items = nat
 182                 _length = size
 183         end
 184
 185         # Create a new string from a null terminated char *.
 186         init from_cstring(str: NativeString)
 187         do
 188                 var size = str.cstring_length
 189                 _items = str
 190                 _length = size
 191         end
 192
 193         # Return a null terminated char *
 194         fun to_cstring: NativeString
 195         do
 196                 return _items
 197         end
 198
 199         redef fun ==(o)
 200         do
 201                 if not o isa String or o is null then return false
 202                 var l = length
 203                 if o.length != l then return false
 204                 var i = 0
 205                 var it = _items
 206                 var oit = o._items
 207                 while i < l do
 208                         if it[i] != oit[i] then return false
 209                         i += 1
 210                 end
 211                 return true
 212         end
 213
 214         redef fun <(s)
 215         do
 216                 var i = 0
 217                 var l1 = length
 218                 var l2 = s.length
 219                 var n1 = _items
 220                 var n2 = s._items
 221                 while i < l1 and i < l2 do
 222                         var c1 = n1[i].ascii
 223                         var c2 = n2[i].ascii
 224                         if c1 < c2 then
 225                                 return true
 226                         else if c2 < c1 then
 227                                 return false
 228                         end
 229                         i += 1
 230                 end
 231                 if l1 < l2 then
 232                         return true
 233                 else
 234                         return false
 235                 end
 236         end
 237
 238         # The concatenation of `self' with `r'
 239         fun +(s: String): String
 240         do
 241                 var r = new Buffer.with_capacity(length + s.length)
 242                 r.append(self)
 243                 r.append(s)
 244                 return r.to_s
 245         end
 246
 247         # i repetitions of self
 248         fun *(i: Int): String
 249         do
 250                 assert i >= 0
 251                 var r = new Buffer.with_capacity(length * i)
 252                 while i > 0 do
 253                         r.append(self)
 254                         i -= 1
 255                 end
 256                 return r.to_s
 257         end
 258
 259         redef fun to_s do return self
 260
 261         redef fun hash
 262         do
 263                 # djb2 hash algorythm
 264                 var h = 5381
 265                 var i = _length - 1
 266                 var it = _items
 267                 while i >= 0 do
 268                         h = (h * 32) + h + it[i].ascii
 269                         i -= 1
 270                 end
 271                 return h
 272
 273         end
 274 end
 275
 276 # Mutable strings of characters.
 277 class Buffer
 278         super AbstractString
 279         super Comparable
 280         super StringCapable
 281         super AbstractArray[Char]
 282
 283         redef type OTHER: String
 284
 285         redef fun []=(index, item)
 286         do
 287                 if index == length then
 288                         add(item)
 289                         return
 290                 end
 291                 assert index >= 0 and index < length
 292                 _items[index] = item
 293         end
 294
 295         redef fun add(c)
 296         do
 297                 if _capacity <= length then enlarge(length + 5)
 298                 _items[length] = c
 299                 _length += 1
 300         end
 301
 302         redef fun enlarge(cap)
 303         do
 304                 var c = _capacity
 305                 if cap <= c then return
 306                 while c <= cap do c = c * 2 + 2
 307                 var a = calloc_string(c+1)
 308                 _items.copy_to(a, length, 0, 0)
 309                 _items = a
 310                 _capacity = c
 311         end
 312
 313         redef fun append(s)
 314         do
 315                 if s isa String then
 316                         var sl = s.length
 317                         if _capacity < length + sl then enlarge(length + sl)
 318                         s.items.copy_to(_items, sl, 0, length)
 319                         _length += sl
 320                 else
 321                         super
 322                 end
 323         end
 324
 325         redef fun to_s: String
 326         do
 327                 var l = length
 328                 var a = calloc_string(l+1)
 329                 _items.copy_to(a, l, 0, 0)
 330
 331                 # Ensure the afterlast byte is '\0' to nul-terminated char *
 332                 a[length] = '\0'
 333
 334                 return new String.with_native(a, length)
 335         end
 336
 337         redef fun <(s)
 338         do
 339                 var i = 0
 340                 var l1 = length
 341                 var l2 = s.length
 342                 while i < l1 and i < l2 do
 343                         var c1 = self[i].ascii
 344                         var c2 = s[i].ascii
 345                         if c1 < c2 then
 346                                 return true
 347                         else if c2 < c1 then
 348                                 return false
 349                         end
 350                         i += 1
 351                 end
 352                 if l1 < l2 then
 353                         return true
 354                 else
 355                         return false
 356                 end
 357         end
 358
 359         # Create a new empty string.
 360         init
 361         do
 362                 with_capacity(5)
 363         end
 364
 365         init from(s: String)
 366         do
 367                 _capacity = s.length + 1
 368                 _length = s.length
 369                 _items = calloc_string(_capacity)
 370                 s.items.copy_to(_items, _length, 0, 0)
 371         end
 372
 373         # Create a new empty string with a given capacity.
 374         init with_capacity(cap: Int)
 375         do
 376                 assert cap >= 0
 377                 # _items = new NativeString.calloc(cap)
 378                 _items = calloc_string(cap+1)
 379                 _capacity = cap
 380                 _length = 0
 381         end
 382
 383         redef fun ==(o)
 384         do
 385                 if not o isa Buffer or o is null then return false
 386                 var l = length
 387                 if o.length != l then return false
 388                 var i = 0
 389                 var it = _items
 390                 var oit = o._items
 391                 while i < l do
 392                         if it[i] != oit[i] then return false
 393                         i += 1
 394                 end
 395                 return true
 396         end
 397
 398         readable private var _capacity: Int
 399 end
 400
 401 ###############################################################################
 402 # Refinement                                                                  #
 403 ###############################################################################
 404
 405 redef class Object
 406         # User readable representation of `self'.
 407         fun to_s: String do return inspect
 408
 409         # The class name of the object in NativeString format.
 410         private fun native_class_name: NativeString is intern
 411
 412         # The class name of the object.
 413         # FIXME: real type information is not available at runtime.
 414         # Therefore, for instance, an instance of List[Bool] has just
 415         # "List" for class_name
 416         fun class_name: String do return new String.from_cstring(native_class_name)
 417
 418         # Developer readable representation of `self'.
 419         # Usually, it uses the form "<CLASSNAME:#OBJECTID bla bla bla>"
 420         fun inspect: String
 421         do
 422                 return "<{inspect_head}>"
 423         end
 424
 425         # Return "CLASSNAME:#OBJECTID".
 426         # This function is mainly used with the redefinition of the inspect method
 427         protected fun inspect_head: String
 428         do
 429                 return "{class_name}:#{object_id.to_hex}"
 430         end
 431
 432         protected fun args: Sequence[String]
 433         do
 434                 return sys.args
 435         end
 436 end
 437
 438 redef class Bool
 439         redef fun to_s
 440         do
 441                 if self then
 442                         return once "true"
 443                 else
 444                         return once "false"
 445                 end
 446         end
 447 end
 448
 449 redef class Int
 450         fun fill_buffer(s: Buffer, base: Int, signed: Bool)
 451         # Fill `s' with the digits in base 'base' of `self' (and with the '-' sign if 'signed' and negative).
 452         # assume < to_c max const of char
 453         do
 454                 var n: Int
 455                 # Sign
 456                 if self < 0 then
 457                         n = - self
 458                         s[0] = '-'
 459                 else if self == 0 then
 460                         s[0] = '0'
 461                         return
 462                 else
 463                         n = self
 464                 end
 465                 # Fill digits
 466                 var pos = digit_count(base) - 1
 467                 while pos >= 0 and n > 0 do
 468                         s[pos] = (n % base).to_c
 469                         n = n / base # /
 470                         pos -= 1
 471                 end
 472         end
 473
 474         # return displayable int in base 10 and signed
 475         redef fun to_s do return to_base(10,true)
 476
 477         # return displayable int in hexadecimal (unsigned (not now))
 478         fun to_hex: String do return to_base(16,false)
 479
 480         # return displayable int in base base and signed
 481         fun to_base(base: Int, signed: Bool): String
 482         do
 483                 var l = digit_count(base)
 484                 var s = new Buffer.from(" " * l)
 485                 fill_buffer(s, base, signed)
 486                 return s.to_s
 487         end
 488 end
 489
 490 redef class Float
 491         # Pretty print self, print needed decimals up to a max of 6.
 492         redef fun to_s do
 493                 var str = to_precision( 6 )
 494                 var len = str.length
 495                 for i in [0..len-1] do
 496                         var j = len-1-i
 497                         var c = str[j]
 498                         if c == '0' then
 499                                 continue
 500                         else if c == '.' then
 501                                 return str.substring( 0, j+2 )
 502                         else
 503                                 return str.substring( 0, j+1 )
 504                         end
 505                 end
 506                 return str
 507         end
 508
 509         # `self' representation with `nb' digits after the '.'.
 510         fun to_precision(nb: Int): String import String::from_cstring `{
 511                 int size;
 512                 char *str;
 513
 514                 size = snprintf(NULL, 0, "%.*f", (int)nb, recv);
 515                 str = malloc(size + 1);
 516                 sprintf(str, "%.*f", (int)nb, recv );
 517
 518                 return new_String_from_cstring( str );
 519         `}
 520 end
 521
 522 redef class Char
 523         redef fun to_s
 524         do
 525                 var s = new Buffer.with_capacity(1)
 526                 s[0] = self
 527                 return s.to_s
 528         end
 529 end
 530
 531 redef class Collection[E]
 532         # Concatenate elements.
 533         redef fun to_s
 534         do
 535                 var s = new Buffer
 536                 for e in self do if e != null then s.append(e.to_s)
 537                 return s.to_s
 538         end
 539
 540         # Concatenate and separate each elements with `sep'.
 541         fun join(sep: String): String
 542         do
 543                 if is_empty then return ""
 544
 545                 var s = new Buffer # Result
 546
 547                 # Concat first item
 548                 var i = iterator
 549                 var e = i.item
 550                 if e != null then s.append(e.to_s)
 551
 552                 # Concat other items
 553                 i.next
 554                 while i.is_ok do
 555                         s.append(sep)
 556                         e = i.item
 557                         if e != null then s.append(e.to_s)
 558                         i.next
 559                 end
 560                 return s.to_s
 561         end
 562 end
 563
 564 redef class Array[E]
 565         # Fast implementation
 566         redef fun to_s
 567         do
 568                 var s = new Buffer
 569                 var i = 0
 570                 var l = length
 571                 while i < l do
 572                         var e = self[i]
 573                         if e != null then s.append(e.to_s)
 574                         i += 1
 575                 end
 576                 return s.to_s
 577         end
 578 end
 579
 580 redef class Map[K,V]
 581         # Concatenate couple of 'key value'.
 582         # key and value are separated by 'couple_sep'.
 583         # each couple is separated each couple with `sep'.
 584         fun join(sep: String, couple_sep: String): String
 585         do
 586                 if is_empty then return ""
 587
 588                 var s = new Buffer # Result
 589
 590                 # Concat first item
 591                 var i = iterator
 592                 var k = i.key
 593                 var e = i.item
 594                 if e != null then s.append("{k}{couple_sep}{e}")
 595
 596                 # Concat other items
 597                 i.next
 598                 while i.is_ok do
 599                         s.append(sep)
 600                         k = i.key
 601                         e = i.item
 602                         if e != null then s.append("{k}{couple_sep}{e}")
 603                         i.next
 604                 end
 605                 return s.to_s
 606         end
 607 end
 608
 609 ###############################################################################
 610 # Native classes                                                              #
 611 ###############################################################################
 612
 613 # Native strings are simple C char *
 614 class NativeString
 615         fun [](index: Int): Char is intern
 616         fun []=(index: Int, item: Char) is intern
 617         fun copy_to(dest: NativeString, length: Int, from: Int, to: Int) is intern
 618
 619         # Position of the first nul character.
 620         fun cstring_length: Int
 621         do
 622                 var l = 0
 623                 while self[l] != '\0' do l += 1
 624                 return l
 625         end
 626         fun atoi: Int is intern
 627         fun atof: Float is extern "atof"
 628 end
 629
 630 # StringCapable objects can create native strings
 631 interface StringCapable
 632         protected fun calloc_string(size: Int): NativeString is intern
 633 end
 634
 635 redef class Sys
 636         var _args_cache: nullable Sequence[String]
 637
 638         redef fun args: Sequence[String]
 639         do
 640                 if _args_cache == null then init_args
 641                 return _args_cache.as(not null)
 642         end
 643
 644         # The name of the program as given by the OS
 645         fun program_name: String
 646         do
 647                 return new String.from_cstring(native_argv(0))
 648         end
 649
 650         # Initialize `args' with the contents of `native_argc' and `native_argv'.
 651         private fun init_args
 652         do
 653                 var argc = native_argc
 654                 var args = new Array[String].with_capacity(0)
 655                 var i = 1
 656                 while i < argc do
 657                         args[i-1] = new String.from_cstring(native_argv(i))
 658                         i += 1
 659                 end
 660                 _args_cache = args
 661         end
 662
 663         private fun native_argc: Int is extern "kernel_Sys_Sys_native_argc_0" # First argument of the main C function.
 664
 665         private fun native_argv(i: Int): NativeString is extern "kernel_Sys_Sys_native_argv_1" # Second argument of the main C function.
 666 end
 667