review.tizen.org Git - platform/framework/web/crosswalk-tizen.git/blob

   1 /*
   2   Copyright (C) 2012-2014 Yusuke Suzuki <utatane.tea@gmail.com>
   3   Copyright (C) 2014 Dan Tao <daniel.tao@gmail.com>
   4   Copyright (C) 2013 Andrew Eisenberg <andrew@eisenberg.as>
   5
   6   Redistribution and use in source and binary forms, with or without
   7   modification, are permitted provided that the following conditions are met:
   8
   9     * Redistributions of source code must retain the above copyright
  10       notice, this list of conditions and the following disclaimer.
  11     * Redistributions in binary form must reproduce the above copyright
  12       notice, this list of conditions and the following disclaimer in the
  13       documentation and/or other materials provided with the distribution.
  14
  15   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16   AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18   ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
  19   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  20   (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  21   LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  22   ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24   THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25 */
  26
  27 // "typed", the Type Expression Parser for doctrine.
  28
  29 (function () {
  30     'use strict';
  31
  32     var Syntax,
  33         Token,
  34         source,
  35         length,
  36         index,
  37         previous,
  38         token,
  39         value,
  40         esutils,
  41         utility;
  42
  43     esutils = require('esutils');
  44     utility = require('./utility');
  45
  46     Syntax = {
  47         NullableLiteral: 'NullableLiteral',
  48         AllLiteral: 'AllLiteral',
  49         NullLiteral: 'NullLiteral',
  50         UndefinedLiteral: 'UndefinedLiteral',
  51         VoidLiteral: 'VoidLiteral',
  52         UnionType: 'UnionType',
  53         ArrayType: 'ArrayType',
  54         RecordType: 'RecordType',
  55         FieldType: 'FieldType',
  56         FunctionType: 'FunctionType',
  57         ParameterType: 'ParameterType',
  58         RestType: 'RestType',
  59         NonNullableType: 'NonNullableType',
  60         OptionalType: 'OptionalType',
  61         NullableType: 'NullableType',
  62         NameExpression: 'NameExpression',
  63         TypeApplication: 'TypeApplication'
  64     };
  65
  66     Token = {
  67         ILLEGAL: 0,    // ILLEGAL
  68         DOT_LT: 1,     // .<
  69         REST: 2,       // ...
  70         LT: 3,         // <
  71         GT: 4,         // >
  72         LPAREN: 5,     // (
  73         RPAREN: 6,     // )
  74         LBRACE: 7,     // {
  75         RBRACE: 8,     // }
  76         LBRACK: 9,    // [
  77         RBRACK: 10,    // ]
  78         COMMA: 11,     // ,
  79         COLON: 12,     // :
  80         STAR: 13,      // *
  81         PIPE: 14,      // |
  82         QUESTION: 15,  // ?
  83         BANG: 16,      // !
  84         EQUAL: 17,     // =
  85         NAME: 18,      // name token
  86         STRING: 19,    // string
  87         NUMBER: 20,    // number
  88         EOF: 21
  89     };
  90
  91     function isTypeName(ch) {
  92         return '><(){}[],:*|?!='.indexOf(String.fromCharCode(ch)) === -1 && !esutils.code.isWhiteSpace(ch) && !esutils.code.isLineTerminator(ch);
  93     }
  94
  95     function Context(previous, index, token, value) {
  96         this._previous = previous;
  97         this._index = index;
  98         this._token = token;
  99         this._value = value;
 100     }
 101
 102     Context.prototype.restore = function () {
 103         previous = this._previous;
 104         index = this._index;
 105         token = this._token;
 106         value = this._value;
 107     };
 108
 109     Context.save = function () {
 110         return new Context(previous, index, token, value);
 111     };
 112
 113     function advance() {
 114         var ch = source.charAt(index);
 115         index += 1;
 116         return ch;
 117     }
 118
 119     function scanHexEscape(prefix) {
 120         var i, len, ch, code = 0;
 121
 122         len = (prefix === 'u') ? 4 : 2;
 123         for (i = 0; i < len; ++i) {
 124             if (index < length && esutils.code.isHexDigit(source.charCodeAt(index))) {
 125                 ch = advance();
 126                 code = code * 16 + '0123456789abcdef'.indexOf(ch.toLowerCase());
 127             } else {
 128                 return '';
 129             }
 130         }
 131         return String.fromCharCode(code);
 132     }
 133
 134     function scanString() {
 135         var str = '', quote, ch, code, unescaped, restore; //TODO review removal octal = false
 136         quote = source.charAt(index);
 137         ++index;
 138
 139         while (index < length) {
 140             ch = advance();
 141
 142             if (ch === quote) {
 143                 quote = '';
 144                 break;
 145             } else if (ch === '\\') {
 146                 ch = advance();
 147                 if (!esutils.code.isLineTerminator(ch.charCodeAt(0))) {
 148                     switch (ch) {
 149                     case 'n':
 150                         str += '\n';
 151                         break;
 152                     case 'r':
 153                         str += '\r';
 154                         break;
 155                     case 't':
 156                         str += '\t';
 157                         break;
 158                     case 'u':
 159                     case 'x':
 160                         restore = index;
 161                         unescaped = scanHexEscape(ch);
 162                         if (unescaped) {
 163                             str += unescaped;
 164                         } else {
 165                             index = restore;
 166                             str += ch;
 167                         }
 168                         break;
 169                     case 'b':
 170                         str += '\b';
 171                         break;
 172                     case 'f':
 173                         str += '\f';
 174                         break;
 175                     case 'v':
 176                         str += '\v';
 177                         break;
 178
 179                     default:
 180                         if (esutils.code.isOctalDigit(ch.charCodeAt(0))) {
 181                             code = '01234567'.indexOf(ch);
 182
 183                             // \0 is not octal escape sequence
 184                             // Deprecating unused code. TODO review removal
 185                             //if (code !== 0) {
 186                             //    octal = true;
 187                             //}
 188
 189                             if (index < length && esutils.code.isOctalDigit(source.charCodeAt(index))) {
 190                                 //TODO Review Removal octal = true;
 191                                 code = code * 8 + '01234567'.indexOf(advance());
 192
 193                                 // 3 digits are only allowed when string starts
 194                                 // with 0, 1, 2, 3
 195                                 if ('0123'.indexOf(ch) >= 0 &&
 196                                         index < length &&
 197                                         esutils.code.isOctalDigit(source.charCodeAt(index))) {
 198                                     code = code * 8 + '01234567'.indexOf(advance());
 199                                 }
 200                             }
 201                             str += String.fromCharCode(code);
 202                         } else {
 203                             str += ch;
 204                         }
 205                         break;
 206                     }
 207                 } else {
 208                     if (ch ===  '\r' && source.charCodeAt(index) === 0x0A  /* '\n' */) {
 209                         ++index;
 210                     }
 211                 }
 212             } else if (esutils.code.isLineTerminator(ch.charCodeAt(0))) {
 213                 break;
 214             } else {
 215                 str += ch;
 216             }
 217         }
 218
 219         if (quote !== '') {
 220             utility.throwError('unexpected quote');
 221         }
 222
 223         value = str;
 224         return Token.STRING;
 225     }
 226
 227     function scanNumber() {
 228         var number, ch;
 229
 230         number = '';
 231         ch = source.charCodeAt(index);
 232
 233         if (ch !== 0x2E  /* '.' */) {
 234             number = advance();
 235             ch = source.charCodeAt(index);
 236
 237             if (number === '0') {
 238                 if (ch === 0x78  /* 'x' */ || ch === 0x58  /* 'X' */) {
 239                     number += advance();
 240                     while (index < length) {
 241                         ch = source.charCodeAt(index);
 242                         if (!esutils.code.isHexDigit(ch)) {
 243                             break;
 244                         }
 245                         number += advance();
 246                     }
 247
 248                     if (number.length <= 2) {
 249                         // only 0x
 250                         utility.throwError('unexpected token');
 251                     }
 252
 253                     if (index < length) {
 254                         ch = source.charCodeAt(index);
 255                         if (esutils.code.isIdentifierStart(ch)) {
 256                             utility.throwError('unexpected token');
 257                         }
 258                     }
 259                     value = parseInt(number, 16);
 260                     return Token.NUMBER;
 261                 }
 262
 263                 if (esutils.code.isOctalDigit(ch)) {
 264                     number += advance();
 265                     while (index < length) {
 266                         ch = source.charCodeAt(index);
 267                         if (!esutils.code.isOctalDigit(ch)) {
 268                             break;
 269                         }
 270                         number += advance();
 271                     }
 272
 273                     if (index < length) {
 274                         ch = source.charCodeAt(index);
 275                         if (esutils.code.isIdentifierStart(ch) || esutils.code.isDecimalDigit(ch)) {
 276                             utility.throwError('unexpected token');
 277                         }
 278                     }
 279                     value = parseInt(number, 8);
 280                     return Token.NUMBER;
 281                 }
 282
 283                 if (esutils.code.isDecimalDigit(ch)) {
 284                     utility.throwError('unexpected token');
 285                 }
 286             }
 287
 288             while (index < length) {
 289                 ch = source.charCodeAt(index);
 290                 if (!esutils.code.isDecimalDigit(ch)) {
 291                     break;
 292                 }
 293                 number += advance();
 294             }
 295         }
 296
 297         if (ch === 0x2E  /* '.' */) {
 298             number += advance();
 299             while (index < length) {
 300                 ch = source.charCodeAt(index);
 301                 if (!esutils.code.isDecimalDigit(ch)) {
 302                     break;
 303                 }
 304                 number += advance();
 305             }
 306         }
 307
 308         if (ch === 0x65  /* 'e' */ || ch === 0x45  /* 'E' */) {
 309             number += advance();
 310
 311             ch = source.charCodeAt(index);
 312             if (ch === 0x2B  /* '+' */ || ch === 0x2D  /* '-' */) {
 313                 number += advance();
 314             }
 315
 316             ch = source.charCodeAt(index);
 317             if (esutils.code.isDecimalDigit(ch)) {
 318                 number += advance();
 319                 while (index < length) {
 320                     ch = source.charCodeAt(index);
 321                     if (!esutils.code.isDecimalDigit(ch)) {
 322                         break;
 323                     }
 324                     number += advance();
 325                 }
 326             } else {
 327                 utility.throwError('unexpected token');
 328             }
 329         }
 330
 331         if (index < length) {
 332             ch = source.charCodeAt(index);
 333             if (esutils.code.isIdentifierStart(ch)) {
 334                 utility.throwError('unexpected token');
 335             }
 336         }
 337
 338         value = parseFloat(number);
 339         return Token.NUMBER;
 340     }
 341
 342
 343     function scanTypeName() {
 344         var ch, ch2;
 345
 346         value = advance();
 347         while (index < length && isTypeName(source.charCodeAt(index))) {
 348             ch = source.charCodeAt(index);
 349             if (ch === 0x2E  /* '.' */) {
 350                 if ((index + 1) >= length) {
 351                     return Token.ILLEGAL;
 352                 }
 353                 ch2 = source.charCodeAt(index + 1);
 354                 if (ch2 === 0x3C  /* '<' */) {
 355                     break;
 356                 }
 357             }
 358             value += advance();
 359         }
 360         return Token.NAME;
 361     }
 362
 363     function next() {
 364         var ch;
 365
 366         previous = index;
 367
 368         while (index < length && esutils.code.isWhiteSpace(source.charCodeAt(index))) {
 369             advance();
 370         }
 371         if (index >= length) {
 372             token = Token.EOF;
 373             return token;
 374         }
 375
 376         ch = source.charCodeAt(index);
 377         switch (ch) {
 378         case 0x27:  /* ''' */
 379         case 0x22:  /* '"' */
 380             token = scanString();
 381             return token;
 382
 383         case 0x3A:  /* ':' */
 384             advance();
 385             token = Token.COLON;
 386             return token;
 387
 388         case 0x2C:  /* ',' */
 389             advance();
 390             token = Token.COMMA;
 391             return token;
 392
 393         case 0x28:  /* '(' */
 394             advance();
 395             token = Token.LPAREN;
 396             return token;
 397
 398         case 0x29:  /* ')' */
 399             advance();
 400             token = Token.RPAREN;
 401             return token;
 402
 403         case 0x5B:  /* '[' */
 404             advance();
 405             token = Token.LBRACK;
 406             return token;
 407
 408         case 0x5D:  /* ']' */
 409             advance();
 410             token = Token.RBRACK;
 411             return token;
 412
 413         case 0x7B:  /* '{' */
 414             advance();
 415             token = Token.LBRACE;
 416             return token;
 417
 418         case 0x7D:  /* '}' */
 419             advance();
 420             token = Token.RBRACE;
 421             return token;
 422
 423         case 0x2E:  /* '.' */
 424             if (index + 1 < length) {
 425                 ch = source.charCodeAt(index + 1);
 426                 if (ch === 0x3C  /* '<' */) {
 427                     advance();  // '.'
 428                     advance();  // '<'
 429                     token = Token.DOT_LT;
 430                     return token;
 431                 }
 432
 433                 if (ch === 0x2E  /* '.' */ && index + 2 < length && source.charCodeAt(index + 2) === 0x2E  /* '.' */) {
 434                     advance();  // '.'
 435                     advance();  // '.'
 436                     advance();  // '.'
 437                     token = Token.REST;
 438                     return token;
 439                 }
 440
 441                 if (esutils.code.isDecimalDigit(ch)) {
 442                     token = scanNumber();
 443                     return token;
 444                 }
 445             }
 446             token = Token.ILLEGAL;
 447             return token;
 448
 449         case 0x3C:  /* '<' */
 450             advance();
 451             token = Token.LT;
 452             return token;
 453
 454         case 0x3E:  /* '>' */
 455             advance();
 456             token = Token.GT;
 457             return token;
 458
 459         case 0x2A:  /* '*' */
 460             advance();
 461             token = Token.STAR;
 462             return token;
 463
 464         case 0x7C:  /* '|' */
 465             advance();
 466             token = Token.PIPE;
 467             return token;
 468
 469         case 0x3F:  /* '?' */
 470             advance();
 471             token = Token.QUESTION;
 472             return token;
 473
 474         case 0x21:  /* '!' */
 475             advance();
 476             token = Token.BANG;
 477             return token;
 478
 479         case 0x3D:  /* '=' */
 480             advance();
 481             token = Token.EQUAL;
 482             return token;
 483
 484         default:
 485             if (esutils.code.isDecimalDigit(ch)) {
 486                 token = scanNumber();
 487                 return token;
 488             }
 489
 490             // type string permits following case,
 491             //
 492             // namespace.module.MyClass
 493             //
 494             // this reduced 1 token TK_NAME
 495             utility.assert(isTypeName(ch));
 496             token = scanTypeName();
 497             return token;
 498         }
 499     }
 500
 501     function consume(target, text) {
 502         utility.assert(token === target, text || 'consumed token not matched');
 503         next();
 504     }
 505
 506     function expect(target, message) {
 507         if (token !== target) {
 508             utility.throwError(message || 'unexpected token');
 509         }
 510         next();
 511     }
 512
 513     // UnionType := '(' TypeUnionList ')'
 514     //
 515     // TypeUnionList :=
 516     //     <<empty>>
 517     //   | NonemptyTypeUnionList
 518     //
 519     // NonemptyTypeUnionList :=
 520     //     TypeExpression
 521     //   | TypeExpression '|' NonemptyTypeUnionList
 522     function parseUnionType() {
 523         var elements;
 524         consume(Token.LPAREN, 'UnionType should start with (');
 525         elements = [];
 526         if (token !== Token.RPAREN) {
 527             while (true) {
 528                 elements.push(parseTypeExpression());
 529                 if (token === Token.RPAREN) {
 530                     break;
 531                 }
 532                 expect(Token.PIPE);
 533             }
 534         }
 535         consume(Token.RPAREN, 'UnionType should end with )');
 536         return {
 537             type: Syntax.UnionType,
 538             elements: elements
 539         };
 540     }
 541
 542     // ArrayType := '[' ElementTypeList ']'
 543     //
 544     // ElementTypeList :=
 545     //     <<empty>>
 546     //  | TypeExpression
 547     //  | '...' TypeExpression
 548     //  | TypeExpression ',' ElementTypeList
 549     function parseArrayType() {
 550         var elements;
 551         consume(Token.LBRACK, 'ArrayType should start with [');
 552         elements = [];
 553         while (token !== Token.RBRACK) {
 554             if (token === Token.REST) {
 555                 consume(Token.REST);
 556                 elements.push({
 557                     type: Syntax.RestType,
 558                     expression: parseTypeExpression()
 559                 });
 560                 break;
 561             } else {
 562                 elements.push(parseTypeExpression());
 563             }
 564             if (token !== Token.RBRACK) {
 565                 expect(Token.COMMA);
 566             }
 567         }
 568         expect(Token.RBRACK);
 569         return {
 570             type: Syntax.ArrayType,
 571             elements: elements
 572         };
 573     }
 574
 575     function parseFieldName() {
 576         var v = value;
 577         if (token === Token.NAME || token === Token.STRING) {
 578             next();
 579             return v;
 580         }
 581
 582         if (token === Token.NUMBER) {
 583             consume(Token.NUMBER);
 584             return String(v);
 585         }
 586
 587         utility.throwError('unexpected token');
 588     }
 589
 590     // FieldType :=
 591     //     FieldName
 592     //   | FieldName ':' TypeExpression
 593     //
 594     // FieldName :=
 595     //     NameExpression
 596     //   | StringLiteral
 597     //   | NumberLiteral
 598     //   | ReservedIdentifier
 599     function parseFieldType() {
 600         var key;
 601
 602         key = parseFieldName();
 603         if (token === Token.COLON) {
 604             consume(Token.COLON);
 605             return {
 606                 type: Syntax.FieldType,
 607                 key: key,
 608                 value: parseTypeExpression()
 609             };
 610         }
 611         return {
 612             type: Syntax.FieldType,
 613             key: key,
 614             value: null
 615         };
 616     }
 617
 618     // RecordType := '{' FieldTypeList '}'
 619     //
 620     // FieldTypeList :=
 621     //     <<empty>>
 622     //   | FieldType
 623     //   | FieldType ',' FieldTypeList
 624     function parseRecordType() {
 625         var fields;
 626
 627         consume(Token.LBRACE, 'RecordType should start with {');
 628         fields = [];
 629         if (token === Token.COMMA) {
 630             consume(Token.COMMA);
 631         } else {
 632             while (token !== Token.RBRACE) {
 633                 fields.push(parseFieldType());
 634                 if (token !== Token.RBRACE) {
 635                     expect(Token.COMMA);
 636                 }
 637             }
 638         }
 639         expect(Token.RBRACE);
 640         return {
 641             type: Syntax.RecordType,
 642             fields: fields
 643         };
 644     }
 645
 646     // NameExpression :=
 647     //    Identifier
 648     //  | TagIdentifier ':' Identifier
 649     //
 650     // Tag identifier is one of "module", "external" or "event"
 651     // Identifier is the same as Token.NAME, including any dots, something like
 652     // namespace.module.MyClass
 653     function parseNameExpression() {
 654         var name = value;
 655         expect(Token.NAME);
 656
 657         if (token === Token.COLON && (
 658                 name === 'module' ||
 659                 name === 'external' ||
 660                 name === 'event')) {
 661             consume(Token.COLON);
 662             name += ':' + value;
 663             expect(Token.NAME);
 664         }
 665
 666         return {
 667             type: Syntax.NameExpression,
 668             name: name
 669         };
 670     }
 671
 672     // TypeExpressionList :=
 673     //     TopLevelTypeExpression
 674     //   | TopLevelTypeExpression ',' TypeExpressionList
 675     function parseTypeExpressionList() {
 676         var elements = [];
 677
 678         elements.push(parseTop());
 679         while (token === Token.COMMA) {
 680             consume(Token.COMMA);
 681             elements.push(parseTop());
 682         }
 683         return elements;
 684     }
 685
 686     // TypeName :=
 687     //     NameExpression
 688     //   | NameExpression TypeApplication
 689     //
 690     // TypeApplication :=
 691     //     '.<' TypeExpressionList '>'
 692     //   | '<' TypeExpressionList '>'   // this is extension of doctrine
 693     function parseTypeName() {
 694         var expr, applications;
 695
 696         expr = parseNameExpression();
 697         if (token === Token.DOT_LT || token === Token.LT) {
 698             next();
 699             applications = parseTypeExpressionList();
 700             expect(Token.GT);
 701             return {
 702                 type: Syntax.TypeApplication,
 703                 expression: expr,
 704                 applications: applications
 705             };
 706         }
 707         return expr;
 708     }
 709
 710     // ResultType :=
 711     //     <<empty>>
 712     //   | ':' void
 713     //   | ':' TypeExpression
 714     //
 715     // BNF is above
 716     // but, we remove <<empty>> pattern, so token is always TypeToken::COLON
 717     function parseResultType() {
 718         consume(Token.COLON, 'ResultType should start with :');
 719         if (token === Token.NAME && value === 'void') {
 720             consume(Token.NAME);
 721             return {
 722                 type: Syntax.VoidLiteral
 723             };
 724         }
 725         return parseTypeExpression();
 726     }
 727
 728     // ParametersType :=
 729     //     RestParameterType
 730     //   | NonRestParametersType
 731     //   | NonRestParametersType ',' RestParameterType
 732     //
 733     // RestParameterType :=
 734     //     '...'
 735     //     '...' Identifier
 736     //
 737     // NonRestParametersType :=
 738     //     ParameterType ',' NonRestParametersType
 739     //   | ParameterType
 740     //   | OptionalParametersType
 741     //
 742     // OptionalParametersType :=
 743     //     OptionalParameterType
 744     //   | OptionalParameterType, OptionalParametersType
 745     //
 746     // OptionalParameterType := ParameterType=
 747     //
 748     // ParameterType := TypeExpression | Identifier ':' TypeExpression
 749     //
 750     // Identifier is "new" or "this"
 751     function parseParametersType() {
 752         var params = [], optionalSequence = false, expr, rest = false;
 753
 754         while (token !== Token.RPAREN) {
 755             if (token === Token.REST) {
 756                 // RestParameterType
 757                 consume(Token.REST);
 758                 rest = true;
 759             }
 760
 761             expr = parseTypeExpression();
 762             if (expr.type === Syntax.NameExpression && token === Token.COLON) {
 763                 // Identifier ':' TypeExpression
 764                 consume(Token.COLON);
 765                 expr = {
 766                     type: Syntax.ParameterType,
 767                     name: expr.name,
 768                     expression: parseTypeExpression()
 769                 };
 770             }
 771             if (token === Token.EQUAL) {
 772                 consume(Token.EQUAL);
 773                 expr = {
 774                     type: Syntax.OptionalType,
 775                     expression: expr
 776                 };
 777                 optionalSequence = true;
 778             } else {
 779                 if (optionalSequence) {
 780                     utility.throwError('unexpected token');
 781                 }
 782             }
 783             if (rest) {
 784                 expr = {
 785                     type: Syntax.RestType,
 786                     expression: expr
 787                 };
 788             }
 789             params.push(expr);
 790             if (token !== Token.RPAREN) {
 791                 expect(Token.COMMA);
 792             }
 793         }
 794         return params;
 795     }
 796
 797     // FunctionType := 'function' FunctionSignatureType
 798     //
 799     // FunctionSignatureType :=
 800     //   | TypeParameters '(' ')' ResultType
 801     //   | TypeParameters '(' ParametersType ')' ResultType
 802     //   | TypeParameters '(' 'this' ':' TypeName ')' ResultType
 803     //   | TypeParameters '(' 'this' ':' TypeName ',' ParametersType ')' ResultType
 804     function parseFunctionType() {
 805         var isNew, thisBinding, params, result, fnType;
 806         utility.assert(token === Token.NAME && value === 'function', 'FunctionType should start with \'function\'');
 807         consume(Token.NAME);
 808
 809         // Google Closure Compiler is not implementing TypeParameters.
 810         // So we do not. if we don't get '(', we see it as error.
 811         expect(Token.LPAREN);
 812
 813         isNew = false;
 814         params = [];
 815         thisBinding = null;
 816         if (token !== Token.RPAREN) {
 817             // ParametersType or 'this'
 818             if (token === Token.NAME &&
 819                     (value === 'this' || value === 'new')) {
 820                 // 'this' or 'new'
 821                 // 'new' is Closure Compiler extension
 822                 isNew = value === 'new';
 823                 consume(Token.NAME);
 824                 expect(Token.COLON);
 825                 thisBinding = parseTypeName();
 826                 if (token === Token.COMMA) {
 827                     consume(Token.COMMA);
 828                     params = parseParametersType();
 829                 }
 830             } else {
 831                 params = parseParametersType();
 832             }
 833         }
 834
 835         expect(Token.RPAREN);
 836
 837         result = null;
 838         if (token === Token.COLON) {
 839             result = parseResultType();
 840         }
 841
 842         fnType = {
 843             type: Syntax.FunctionType,
 844             params: params,
 845             result: result
 846         };
 847         if (thisBinding) {
 848             // avoid adding null 'new' and 'this' properties
 849             fnType['this'] = thisBinding;
 850             if (isNew) {
 851                 fnType['new'] = true;
 852             }
 853         }
 854         return fnType;
 855     }
 856
 857     // BasicTypeExpression :=
 858     //     '*'
 859     //   | 'null'
 860     //   | 'undefined'
 861     //   | TypeName
 862     //   | FunctionType
 863     //   | UnionType
 864     //   | RecordType
 865     //   | ArrayType
 866     function parseBasicTypeExpression() {
 867         var context;
 868         switch (token) {
 869         case Token.STAR:
 870             consume(Token.STAR);
 871             return {
 872                 type: Syntax.AllLiteral
 873             };
 874
 875         case Token.LPAREN:
 876             return parseUnionType();
 877
 878         case Token.LBRACK:
 879             return parseArrayType();
 880
 881         case Token.LBRACE:
 882             return parseRecordType();
 883
 884         case Token.NAME:
 885             if (value === 'null') {
 886                 consume(Token.NAME);
 887                 return {
 888                     type: Syntax.NullLiteral
 889                 };
 890             }
 891
 892             if (value === 'undefined') {
 893                 consume(Token.NAME);
 894                 return {
 895                     type: Syntax.UndefinedLiteral
 896                 };
 897             }
 898
 899             context = Context.save();
 900             if (value === 'function') {
 901                 try {
 902                     return parseFunctionType();
 903                 } catch (e) {
 904                     context.restore();
 905                 }
 906             }
 907
 908             return parseTypeName();
 909
 910         default:
 911             utility.throwError('unexpected token');
 912         }
 913     }
 914
 915     // TypeExpression :=
 916     //     BasicTypeExpression
 917     //   | '?' BasicTypeExpression
 918     //   | '!' BasicTypeExpression
 919     //   | BasicTypeExpression '?'
 920     //   | BasicTypeExpression '!'
 921     //   | '?'
 922     //   | BasicTypeExpression '[]'
 923     function parseTypeExpression() {
 924         var expr;
 925
 926         if (token === Token.QUESTION) {
 927             consume(Token.QUESTION);
 928             if (token === Token.COMMA || token === Token.EQUAL || token === Token.RBRACE ||
 929                     token === Token.RPAREN || token === Token.PIPE || token === Token.EOF ||
 930                     token === Token.RBRACK || token === Token.GT) {
 931                 return {
 932                     type: Syntax.NullableLiteral
 933                 };
 934             }
 935             return {
 936                 type: Syntax.NullableType,
 937                 expression: parseBasicTypeExpression(),
 938                 prefix: true
 939             };
 940         }
 941
 942         if (token === Token.BANG) {
 943             consume(Token.BANG);
 944             return {
 945                 type: Syntax.NonNullableType,
 946                 expression: parseBasicTypeExpression(),
 947                 prefix: true
 948             };
 949         }
 950
 951         expr = parseBasicTypeExpression();
 952         if (token === Token.BANG) {
 953             consume(Token.BANG);
 954             return {
 955                 type: Syntax.NonNullableType,
 956                 expression: expr,
 957                 prefix: false
 958             };
 959         }
 960
 961         if (token === Token.QUESTION) {
 962             consume(Token.QUESTION);
 963             return {
 964                 type: Syntax.NullableType,
 965                 expression: expr,
 966                 prefix: false
 967             };
 968         }
 969
 970         if (token === Token.LBRACK) {
 971             consume(Token.LBRACK);
 972             expect(Token.RBRACK, 'expected an array-style type declaration (' + value + '[])');
 973             return {
 974                 type: Syntax.TypeApplication,
 975                 expression: {
 976                     type: Syntax.NameExpression,
 977                     name: 'Array'
 978                 },
 979                 applications: [expr]
 980             };
 981         }
 982
 983         return expr;
 984     }
 985
 986     // TopLevelTypeExpression :=
 987     //      TypeExpression
 988     //    | TypeUnionList
 989     //
 990     // This rule is Google Closure Compiler extension, not ES4
 991     // like,
 992     //   { number | string }
 993     // If strict to ES4, we should write it as
 994     //   { (number|string) }
 995     function parseTop() {
 996         var expr, elements;
 997
 998         expr = parseTypeExpression();
 999         if (token !== Token.PIPE) {
1000             return expr;
1001         }
1002
1003         elements = [ expr ];
1004         consume(Token.PIPE);
1005         while (true) {
1006             elements.push(parseTypeExpression());
1007             if (token !== Token.PIPE) {
1008                 break;
1009             }
1010             consume(Token.PIPE);
1011         }
1012
1013         return {
1014             type: Syntax.UnionType,
1015             elements: elements
1016         };
1017     }
1018
1019     function parseTopParamType() {
1020         var expr;
1021
1022         if (token === Token.REST) {
1023             consume(Token.REST);
1024             return {
1025                 type: Syntax.RestType,
1026                 expression: parseTop()
1027             };
1028         }
1029
1030         expr = parseTop();
1031         if (token === Token.EQUAL) {
1032             consume(Token.EQUAL);
1033             return {
1034                 type: Syntax.OptionalType,
1035                 expression: expr
1036             };
1037         }
1038
1039         return expr;
1040     }
1041
1042     function parseType(src, opt) {
1043         var expr;
1044
1045         source = src;
1046         length = source.length;
1047         index = 0;
1048         previous = 0;
1049
1050         next();
1051         expr = parseTop();
1052
1053         if (opt && opt.midstream) {
1054             return {
1055                 expression: expr,
1056                 index: previous
1057             };
1058         }
1059
1060         if (token !== Token.EOF) {
1061             utility.throwError('not reach to EOF');
1062         }
1063
1064         return expr;
1065     }
1066
1067     function parseParamType(src, opt) {
1068         var expr;
1069
1070         source = src;
1071         length = source.length;
1072         index = 0;
1073         previous = 0;
1074
1075         next();
1076         expr = parseTopParamType();
1077
1078         if (opt && opt.midstream) {
1079             return {
1080                 expression: expr,
1081                 index: previous
1082             };
1083         }
1084
1085         if (token !== Token.EOF) {
1086             utility.throwError('not reach to EOF');
1087         }
1088
1089         return expr;
1090     }
1091
1092     function stringifyImpl(node, compact, topLevel) {
1093         var result, i, iz;
1094
1095         switch (node.type) {
1096         case Syntax.NullableLiteral:
1097             result = '?';
1098             break;
1099
1100         case Syntax.AllLiteral:
1101             result = '*';
1102             break;
1103
1104         case Syntax.NullLiteral:
1105             result = 'null';
1106             break;
1107
1108         case Syntax.UndefinedLiteral:
1109             result = 'undefined';
1110             break;
1111
1112         case Syntax.VoidLiteral:
1113             result = 'void';
1114             break;
1115
1116         case Syntax.UnionType:
1117             if (!topLevel) {
1118                 result = '(';
1119             } else {
1120                 result = '';
1121             }
1122
1123             for (i = 0, iz = node.elements.length; i < iz; ++i) {
1124                 result += stringifyImpl(node.elements[i], compact);
1125                 if ((i + 1) !== iz) {
1126                     result += '|';
1127                 }
1128             }
1129
1130             if (!topLevel) {
1131                 result += ')';
1132             }
1133             break;
1134
1135         case Syntax.ArrayType:
1136             result = '[';
1137             for (i = 0, iz = node.elements.length; i < iz; ++i) {
1138                 result += stringifyImpl(node.elements[i], compact);
1139                 if ((i + 1) !== iz) {
1140                     result += compact ? ',' : ', ';
1141                 }
1142             }
1143             result += ']';
1144             break;
1145
1146         case Syntax.RecordType:
1147             result = '{';
1148             for (i = 0, iz = node.fields.length; i < iz; ++i) {
1149                 result += stringifyImpl(node.fields[i], compact);
1150                 if ((i + 1) !== iz) {
1151                     result += compact ? ',' : ', ';
1152                 }
1153             }
1154             result += '}';
1155             break;
1156
1157         case Syntax.FieldType:
1158             if (node.value) {
1159                 result = node.key + (compact ? ':' : ': ') + stringifyImpl(node.value, compact);
1160             } else {
1161                 result = node.key;
1162             }
1163             break;
1164
1165         case Syntax.FunctionType:
1166             result = compact ? 'function(' : 'function (';
1167
1168             if (node['this']) {
1169                 if (node['new']) {
1170                     result += (compact ? 'new:' : 'new: ');
1171                 } else {
1172                     result += (compact ? 'this:' : 'this: ');
1173                 }
1174
1175                 result += stringifyImpl(node['this'], compact);
1176
1177                 if (node.params.length !== 0) {
1178                     result += compact ? ',' : ', ';
1179                 }
1180             }
1181
1182             for (i = 0, iz = node.params.length; i < iz; ++i) {
1183                 result += stringifyImpl(node.params[i], compact);
1184                 if ((i + 1) !== iz) {
1185                     result += compact ? ',' : ', ';
1186                 }
1187             }
1188
1189             result += ')';
1190
1191             if (node.result) {
1192                 result += (compact ? ':' : ': ') + stringifyImpl(node.result, compact);
1193             }
1194             break;
1195
1196         case Syntax.ParameterType:
1197             result = node.name + (compact ? ':' : ': ') + stringifyImpl(node.expression, compact);
1198             break;
1199
1200         case Syntax.RestType:
1201             result = '...';
1202             if (node.expression) {
1203                 result += stringifyImpl(node.expression, compact);
1204             }
1205             break;
1206
1207         case Syntax.NonNullableType:
1208             if (node.prefix) {
1209                 result = '!' + stringifyImpl(node.expression, compact);
1210             } else {
1211                 result = stringifyImpl(node.expression, compact) + '!';
1212             }
1213             break;
1214
1215         case Syntax.OptionalType:
1216             result = stringifyImpl(node.expression, compact) + '=';
1217             break;
1218
1219         case Syntax.NullableType:
1220             if (node.prefix) {
1221                 result = '?' + stringifyImpl(node.expression, compact);
1222             } else {
1223                 result = stringifyImpl(node.expression, compact) + '?';
1224             }
1225             break;
1226
1227         case Syntax.NameExpression:
1228             result = node.name;
1229             break;
1230
1231         case Syntax.TypeApplication:
1232             result = stringifyImpl(node.expression, compact) + '.<';
1233             for (i = 0, iz = node.applications.length; i < iz; ++i) {
1234                 result += stringifyImpl(node.applications[i], compact);
1235                 if ((i + 1) !== iz) {
1236                     result += compact ? ',' : ', ';
1237                 }
1238             }
1239             result += '>';
1240             break;
1241
1242         default:
1243             utility.throwError('Unknown type ' + node.type);
1244         }
1245
1246         return result;
1247     }
1248
1249     function stringify(node, options) {
1250         if (options == null) {
1251             options = {};
1252         }
1253         return stringifyImpl(node, options.compact, options.topLevel);
1254     }
1255
1256     exports.parseType = parseType;
1257     exports.parseParamType = parseParamType;
1258     exports.stringify = stringify;
1259     exports.Syntax = Syntax;
1260 }());
1261 /* vim: set sw=4 ts=4 et tw=80 : */