lib/standard/kernel.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 # Most minimal classes and methods.
  15 # This module is the root of the standard module hierarchy.
  16 module kernel
  17
  18 import end # Mark this module is a top level one. (must be only one)
  19
  20 ###############################################################################
  21 # System Classes                                                              #
  22 ###############################################################################
  23
  24 # The root of the class hierarchy.
  25 # Each class implicitly specialize Object.
  26 #
  27 # Currently, Object is also used to collect all top-level methods.
  28 interface Object
  29         # Type of this instance, automatically specialized in every class
  30         #
  31         # A common use case of the virtual type `SELF` is to type an attribute and
  32         # store another instance of the same type as `self`. It can also be used as as
  33         # return type to a method producing a copy of `self` or returning an instance
  34         # expected to be the exact same type as self.
  35         #
  36         # This virtual type must be used with caution as it can hinder specialization.
  37         # In fact, it imposes strict restrictions on all sub-classes and their usage.
  38         # For example, using `SELF` as a return type of a method `foo`
  39         # forces all subclasses to ensure that `foo` returns the correct and updated
  40         # type.
  41         # A dangerous usage take the form of a method typed by `SELF` which creates
  42         # and returns a new instance.
  43         # If not correctly specialized, this method would break when invoked on a
  44         # sub-class.
  45         #
  46         # A general rule for safe usage of `SELF` is to ensure that inputs typed
  47         # `SELF` are stored in attributes typed `SELF` and returned by methods typed
  48         # `SELF`, pretty much the same things as you would do with parameter types.
  49         type SELF: Object
  50
  51         # The unique object identifier in the class.
  52         # Unless specific code, you should not use this method.
  53         # The identifier is used internally to provide a hash value.
  54         fun object_id: Int is intern
  55
  56         # Return true if `self` and `other` have the same dynamic type.
  57         # Unless specific code, you should not use this method.
  58         fun is_same_type(other: Object): Bool is intern
  59
  60         # Return true if `self` and `other` are the same instance.
  61         # Unless specific code, you should use `==` instead.
  62         fun is_same_instance(other: nullable Object): Bool is intern
  63
  64         # Have `self` and `other` the same value?
  65         #
  66         # The exact meaning of "same value" is let to the subclasses.
  67         # Implicitly, the default implementation, is `is_same_instance`
  68         fun ==(other: nullable Object): Bool do return self.is_same_instance(other)
  69
  70         # Have `self` and `other` different values?
  71         #
  72         # != is equivalent with "not ==".
  73         fun !=(other: nullable Object): Bool do return not (self == other)
  74
  75         # Display self on stdout (debug only).
  76         # This method MUST not be used by programs, it is here for debugging
  77         # only and can be removed without any notice
  78         fun output
  79         do
  80                 '<'.output
  81                 object_id.output
  82                 '>'.output
  83         end
  84
  85         # Display class name on stdout (debug only).
  86         # This method MUST not be used by programs, it is here for debugging
  87         # only and can be removed without any notice
  88         fun output_class_name is intern
  89
  90         # The hash code of the object.
  91         # Assuming that a == b -> a.hash == b.hash
  92         #
  93         # Without redefinition, it is based on the `object_id` of the instance.
  94         fun hash: Int do return object_id / 8
  95 end
  96
  97 # The main class of the program.
  98 # `Sys` is a singleton class, its only instance is `sys` defined in `Object`.
  99 # `sys` is used to invoke methods on the program on the system.
 100 class Sys
 101         # Instructions outside classes implicitly redefine this method.
 102         fun main do end
 103
 104         # The entry point for the execution of the whole program.
 105         # Its job is to call `main` but some modules may want to refine it
 106         # and inject specific work before or after the main part.
 107         fun run do main
 108
 109         # Number of the last error
 110         fun errno: Int is extern "sys_errno"
 111 end
 112
 113 # Quit the program with a specific return code
 114 fun exit(exit_value: Int) is intern
 115
 116 # Return the global sys object, the only instance of the `Sys` class.
 117 fun sys: Sys is intern
 118
 119
 120 ###############################################################################
 121 # Abstract Classes                                                            #
 122 ###############################################################################
 123
 124 # The ancestor of class where objects are in a total order.
 125 # In order to work, the method '<' has to be redefined.
 126 interface Comparable
 127         # What `self` can be compared to?
 128         type OTHER: Comparable
 129
 130         # Is `self` lesser than `other`?
 131         fun <(other: OTHER): Bool is abstract
 132
 133         # not `other` < `self`
 134         # Note, the implementation must ensure that: `(x<=y) == (x<y or x==y)`
 135         fun <=(other: OTHER): Bool do return not other < self
 136
 137         # not `self` < `other`
 138         # Note, the implementation must ensure that: `(x>=y) == (x>y or x==y)`
 139         fun >=(other: OTHER): Bool do return not self < other
 140
 141         # `other` < `self`
 142         fun >(other: OTHER): Bool do return other < self
 143
 144         # -1 if <, +1 if > and 0 otherwise
 145         # Note, the implementation must ensure that: (x<=>y == 0) == (x==y)
 146         fun <=>(other: OTHER): Int
 147         do
 148                 if self < other then
 149                         return -1
 150                 else if other < self then
 151                         return 1
 152                 else
 153                         return 0
 154                 end
 155         end
 156
 157         # c <= self <= d
 158         fun is_between(c: OTHER, d: OTHER): Bool
 159         do
 160                 return c <= self and self <= d
 161         end
 162
 163         # The maximum between `self` and `other` (prefers `self` if equals).
 164         fun max(other: OTHER): OTHER
 165         do
 166                 if self < other then
 167                         return other
 168                 else
 169                         return self
 170                 end
 171         end
 172
 173         # The minimum between `self` and `c` (prefer `self` if equals)
 174         fun min(c: OTHER): OTHER
 175         do
 176                 if c < self then
 177                         return c
 178                 else
 179                         return self
 180                 end
 181         end
 182 end
 183
 184 # Discrete total orders.
 185 interface Discrete
 186         super Comparable
 187
 188         redef type OTHER: Discrete
 189
 190         # The next element.
 191         fun successor(i: Int): OTHER is abstract
 192
 193         # The previous element.
 194         fun predecessor(i: Int): OTHER is abstract
 195
 196         # The distance between self and d.
 197         #
 198         #     assert 10.distance(15)         ==  5
 199         #     assert 'Z'.distance('A')       ==  25
 200         fun distance(d: OTHER): Int
 201         do
 202                 var cursor: OTHER
 203                 var stop: OTHER
 204                 if self < d then
 205                         cursor = self
 206                         stop = d
 207                 else if self > d then
 208                         cursor = d
 209                         stop = self
 210                 else
 211                         return 0
 212                 end
 213
 214                 var nb = 0
 215                 while cursor < stop do
 216                         cursor = cursor.successor(1)
 217                         nb += 1
 218                 end
 219                 return nb
 220         end
 221 end
 222
 223 # Something that can be cloned
 224 #
 225 # This interface introduces the `clone` method used to duplicate an instance
 226 # Its specific semantic is let to the subclasses.
 227 interface Cloneable
 228         # Duplicate `self`
 229         #
 230         # The specific semantic of this method is let to the subclasses;
 231         # Especially, if (and how) attributes are cloned (depth vs. shallow).
 232         #
 233         # As a rule of thumb, the principle of least astonishment should
 234         # be used to guide the semantic.
 235         #
 236         # Note that as the returned clone depends on the semantic,
 237         # the `==` method, if redefined, should ensure the equality
 238         # between an object and its clone.
 239         fun clone: SELF is abstract
 240 end
 241
 242 # A numeric value supporting mathematical operations
 243 interface Numeric
 244         super Comparable
 245
 246         redef type OTHER: Numeric
 247
 248         # Addition of `self` with `i`
 249         fun +(i: OTHER): OTHER is abstract
 250
 251         # Substraction of `i` from `self`
 252         fun -(i: OTHER): OTHER is abstract
 253
 254         # Inverse of `self`
 255         fun -: OTHER is abstract
 256
 257         # Multiplication of `self` with `i`
 258         fun *(i: OTHER): OTHER is abstract
 259
 260         # Division of `self` with `i`
 261         fun /(i: OTHER): OTHER is abstract
 262
 263         # The integer part of `self`.
 264         #
 265         #     assert (0.0).to_i      == 0
 266         #     assert (0.9).to_i      == 0
 267         #     assert (-0.9).to_i     == 0
 268         #     assert (9.9).to_i      == 9
 269         #     assert (-9.9).to_i     == -9
 270         fun to_i: Int is abstract
 271
 272         # The float equivalent of `self`
 273         #
 274         #     assert 5.to_f         == 5.0
 275         #     assert 5.to_f         != 5 # Float and Int are not equals
 276         fun to_f: Float is abstract
 277
 278         # Is this the value of zero in its domain?
 279         fun is_zero: Bool do return self == zero
 280
 281         # The value of zero in the domain of `self`
 282         fun zero: OTHER is abstract
 283
 284         # The value of `val` in the domain of `self`
 285         #
 286         #     assert 1.0.value_of(2) == 2.0
 287         #     assert 1.0.value_of(2.0) == 2.0
 288         #     assert 1.value_of(2) == 2
 289         #     assert 1.value_of(2.0) == 2
 290         fun value_of(val: Numeric): OTHER is abstract
 291 end
 292
 293 ###############################################################################
 294 # Native classes                                                              #
 295 ###############################################################################
 296
 297 # Native Booleans.
 298 # `true` and `false` are the only instances.
 299 #
 300 # Boolean are manipulated trough three special operators:
 301 # `and`, `or`, `not`.
 302 #
 303 # Booleans are mainly used by conditional statement and loops.
 304 universal Bool
 305         redef fun object_id is intern
 306         redef fun ==(b) is intern
 307         redef fun !=(b) is intern
 308         redef fun output is intern
 309         redef fun hash do return to_i
 310
 311         # 1 if true and 0 if false
 312         fun to_i: Int
 313         do
 314                 if self then
 315                         return 1
 316                 else
 317                         return 0
 318                 end
 319         end
 320 end
 321
 322 # Native floating point numbers.
 323 # Corresponds to C float.
 324 universal Float
 325         super Numeric
 326
 327         redef type OTHER: Float
 328
 329         redef fun object_id is intern
 330         redef fun ==(i) is intern
 331         redef fun !=(i) is intern
 332         redef fun output is intern
 333
 334         redef fun <=(i): Bool is intern
 335         redef fun <(i): Bool is intern
 336         redef fun >=(i): Bool is intern
 337         redef fun >(i): Bool is intern
 338
 339         redef fun +(i) is intern
 340         redef fun - is intern
 341         redef fun -(i) is intern
 342         redef fun *(i) is intern
 343         redef fun /(i) is intern
 344
 345         redef fun to_i is intern
 346         redef fun to_f do return self
 347
 348         redef fun zero do return 0.0
 349         redef fun value_of(val) do return val.to_f
 350
 351         redef fun <=>(other)
 352         do
 353                 if self < other then
 354                         return -1
 355                 else if other < self then
 356                         return 1
 357                 else
 358                         return 0
 359                 end
 360         end
 361
 362         redef fun is_between(c, d)
 363         do
 364                 if self < c or d < self then
 365                         return false
 366                 else
 367                         return true
 368                 end
 369         end
 370
 371         # Compare float numbers with a given precision.
 372         #
 373         # Because of the loss of precision in floating numbers,
 374         # the `==` method is often not the best way to compare them.
 375         #
 376         # ~~~
 377         # assert 0.01.is_approx(0.02, 0.1)   == true
 378         # assert 0.01.is_approx(0.02, 0.001) == false
 379         # ~~~
 380         fun is_approx(other, precision: Float): Bool
 381         do
 382                 assert precision >= 0.0
 383                 return self <= other + precision and self >= other - precision
 384         end
 385
 386         redef fun max(other)
 387         do
 388                 if self < other then
 389                         return other
 390                 else
 391                         return self
 392                 end
 393         end
 394
 395         redef fun min(c)
 396         do
 397                 if c < self then
 398                         return c
 399                 else
 400                         return self
 401                 end
 402         end
 403 end
 404
 405 # Native integer numbers.
 406 # Correspond to C int.
 407 universal Int
 408         super Discrete
 409         super Numeric
 410
 411         redef type OTHER: Int
 412
 413         redef fun successor(i) do return self + i
 414         redef fun predecessor(i) do return self - i
 415
 416         redef fun object_id is intern
 417         redef fun hash do return self
 418         redef fun ==(i) is intern
 419         redef fun !=(i) is intern
 420         redef fun output is intern
 421
 422         redef fun <=(i) is intern
 423         redef fun <(i) is intern
 424         redef fun >=(i) is intern
 425         redef fun >(i) is intern
 426         redef fun +(i) is intern
 427
 428         redef fun - is intern
 429         redef fun -(i) is intern
 430         redef fun *(i) is intern
 431         redef fun /(i) is intern
 432
 433         # Modulo of `self` with `i`.
 434         #
 435         # Finds the remainder of division of `self` by `i`.
 436         #
 437         #     assert 5 % 2                      == 1
 438         #     assert 10 % 2                     == 0
 439         fun %(i: Int): Int is intern
 440
 441         redef fun zero do return 0
 442         redef fun value_of(val) do return val.to_i
 443
 444         # `i` bits shift fo the left (aka <<)
 445         #
 446         #     assert 5.lshift(1)    == 10
 447         fun lshift(i: Int): Int is intern
 448
 449         # `i` bits shift fo the right (aka >>)
 450         #
 451         #     assert 5.rshift(1)    == 2
 452         fun rshift(i: Int): Int is intern
 453
 454         redef fun to_i do return self
 455         redef fun to_f is intern
 456
 457         redef fun distance(i)
 458         do
 459                 var d = self - i
 460                 if d >= 0 then
 461                         return d
 462                 else
 463                         return -d
 464                 end
 465         end
 466
 467         redef fun <=>(other)
 468         do
 469                 if self < other then
 470                         return -1
 471                 else if other < self then
 472                         return 1
 473                 else
 474                         return 0
 475                 end
 476         end
 477
 478         redef fun is_between(c, d)
 479         do
 480                 if self < c or d < self then
 481                         return false
 482                 else
 483                         return true
 484                 end
 485         end
 486
 487         redef fun max(other)
 488         do
 489                 if self < other then
 490                         return other
 491                 else
 492                         return self
 493                 end
 494         end
 495
 496         redef fun min(c)
 497         do
 498                 if c < self then
 499                         return c
 500                 else
 501                         return self
 502                 end
 503         end
 504
 505         # The character whose ASCII value is `self`.
 506         #
 507         #     assert 65.ascii   == 'A'
 508         #     assert 10.ascii   == '\n'
 509         fun ascii: Char is intern
 510
 511         # Number of digits of an integer in base `b` (plus one if negative)
 512         #
 513         #     assert 123.digit_count(10) == 3
 514         #     assert 123.digit_count(2) == 7 # 1111011 in binary
 515         fun digit_count(b: Int): Int
 516         do
 517                 if b == 10 then return digit_count_base_10
 518                 var d: Int # number of digits
 519                 var n: Int # current number
 520                 # Sign
 521                 if self < 0 then
 522                         d = 1
 523                         n = - self
 524                 else if self == 0 then
 525                         return 1
 526                 else
 527                         d = 0
 528                         n = self
 529                 end
 530                 # count digits
 531                 while n > 0 do
 532                         d += 1
 533                         n = n / b       # euclidian division /
 534                 end
 535                 return d
 536         end
 537
 538         # Optimized version for base 10
 539         fun digit_count_base_10: Int
 540         do
 541                 var val: Int
 542                 var result: Int
 543                 if self < 0 then
 544                         result = 2
 545                         val = -self
 546                 else
 547                         result = 1
 548                         val = self
 549                 end
 550                 loop
 551                         if val < 10 then return result
 552                         if val < 100 then return result+1
 553                         if val < 1000 then return result+2
 554                         if val < 10000 then return result+3
 555                         val = val / 10000
 556                         result += 4
 557                 end
 558         end
 559
 560         # Return the corresponding digit character
 561         # If 0 <= `self` <= 9, return the corresponding character.
 562         #     assert 5.to_c    == '5'
 563         # If 10 <= `self` <= 36, return the corresponding letter [a..z].
 564         #     assert 15.to_c   == 'f'
 565         fun to_c: Char
 566         do
 567                 assert self >= 0 and self <= 36 # TODO plan for this
 568                 if self < 10 then
 569                         return (self + '0'.ascii).ascii
 570                 else
 571                         return (self + ('a'.ascii - 10)).ascii
 572                 end
 573         end
 574
 575         # The absolute value of self
 576         #
 577         #     assert (-10).abs   == 10
 578         #     assert 10.abs    == 10
 579         #     assert 0.abs     == 0
 580         fun abs: Int
 581         do
 582             if self >= 0
 583             then
 584                 return self
 585             else
 586                 return -1 * self
 587             end
 588         end
 589 end
 590
 591 # Native characters.
 592 # Characters are denoted with simple quote.
 593 # eg. `'a'` or `'\n'`.
 594 universal Char
 595         super Discrete
 596         redef type OTHER: Char
 597
 598         redef fun object_id is intern
 599         redef fun hash do return ascii
 600         redef fun ==(o) is intern
 601         redef fun !=(o) is intern
 602         redef fun output is intern
 603
 604         redef fun <=(i) is intern
 605         redef fun <(i) is intern
 606         redef fun >=(i) is intern
 607         redef fun >(i) is intern
 608
 609         redef fun successor(i) is intern
 610         redef fun predecessor(i) is intern
 611
 612         redef fun distance(c)
 613         do
 614                 var d = self.ascii - c.ascii
 615                 if d >= 0 then
 616                         return d
 617                 else
 618                         return -d
 619                 end
 620         end
 621
 622         # If `self` is a digit then return this digit else return -1.
 623         #
 624         #     assert '5'.to_i    == 5
 625         fun to_i: Int
 626         do
 627
 628                 if self == '-' then
 629                         return -1
 630                 else if is_digit then
 631                         return self.ascii - '0'.ascii
 632                 else
 633                         return self.to_lower.ascii - 'a'.ascii + 10
 634                 end
 635         end
 636
 637         # the ascii value of self
 638         #
 639         #     assert 'a'.ascii    == 97
 640         #     assert '\n'.ascii   == 10
 641         fun ascii: Int is intern
 642
 643         # Return the lower case version of self.
 644         # If self is not a letter, then return self
 645         #
 646         #     assert 'A'.to_lower  == 'a'
 647         #     assert 'a'.to_lower  == 'a'
 648         #     assert '$'.to_lower  == '$'
 649         fun to_lower: Char
 650         do
 651                 if is_upper then
 652                         return (ascii + ('a'.distance('A'))).ascii
 653                 else
 654                         return self
 655                 end
 656         end
 657
 658         # Return the upper case version of self.
 659         # If self is not a letter, then return self
 660         #
 661         #     assert 'a'.to_upper  == 'A'
 662         #     assert 'A'.to_upper  == 'A'
 663         #     assert '$'.to_upper  == '$'
 664         fun to_upper: Char
 665         do
 666                 if is_lower then
 667                         return (ascii - ('a'.distance('A'))).ascii
 668                 else
 669                         return self
 670                 end
 671         end
 672
 673         # Is self a digit? (from '0' to '9')
 674         #
 675         #     assert '0'.is_digit   == true
 676         #     assert '9'.is_digit   == true
 677         #     assert 'a'.is_digit   == false
 678         fun is_digit : Bool
 679         do
 680                 return self >= '0' and self <= '9'
 681         end
 682
 683         # Is self a lower case letter? (from 'a' to 'z')
 684         #
 685         #     assert 'a'.is_lower   == true
 686         #     assert 'z'.is_lower   == true
 687         #     assert 'A'.is_lower   == false
 688         #     assert '$'.is_lower   == false
 689         fun is_lower : Bool
 690         do
 691                 return self >= 'a' and self <= 'z'
 692         end
 693
 694         # Is self a upper case letter? (from 'A' to 'Z')
 695         #
 696         #     assert 'A'.is_upper   == true
 697         #     assert 'A'.is_upper   == true
 698         #     assert 'z'.is_upper   == false
 699         #     assert '$'.is_upper   == false
 700         fun is_upper : Bool
 701         do
 702                 return self >= 'A' and self <= 'Z'
 703         end
 704
 705         # Is self a letter? (from 'A' to 'Z' and 'a' to 'z')
 706         #
 707         #     assert 'A'.is_letter  == true
 708         #     assert 'A'.is_letter  == true
 709         #     assert 'z'.is_letter  == true
 710         #     assert '$'.is_letter  == false
 711         fun is_letter : Bool
 712         do
 713                 return is_lower or is_upper
 714         end
 715
 716         # Is self a whitespace character?
 717         #
 718         # These correspond to the "Other" and "Separator" groups of the Unicode.
 719         #
 720         # In the ASCII encoding, this is those <= to space (0x20) plus delete (0x7F).
 721         #
 722         #     assert 'A'.is_whitespace  == false
 723         #     assert ','.is_whitespace  == false
 724         #     assert ' '.is_whitespace  == true
 725         #     assert '\t'.is_whitespace == true
 726         fun is_whitespace: Bool
 727         do
 728                 var i = ascii
 729                 return i <= 0x20 or i == 0x7F
 730         end
 731 end
 732
 733 # Pointer classes are used to manipulate extern C structures.
 734 extern class Pointer
 735         # Is the address behind this Object at NULL?
 736         fun address_is_null: Bool is extern "address_is_null"
 737
 738         # Free the memory pointed by this pointer
 739         fun free is extern "free"
 740 end