source/Plugins/ExpressionParser/Go/GoParser.cpp

   1 //===-- GoParser.cpp ---------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include <vector>
  11
  12 #include "GoParser.h"
  13
  14 #include "Plugins/ExpressionParser/Go/GoAST.h"
  15 #include "lldb/Core/Error.h"
  16 #include "llvm/ADT/SmallString.h"
  17
  18 using namespace lldb_private;
  19 using namespace lldb;
  20
  21 namespace {
  22 llvm::StringRef DescribeToken(GoLexer::TokenType t) {
  23   switch (t) {
  24   case GoLexer::TOK_EOF:
  25     return "<eof>";
  26   case GoLexer::TOK_IDENTIFIER:
  27     return "identifier";
  28   case GoLexer::LIT_FLOAT:
  29     return "float";
  30   case GoLexer::LIT_IMAGINARY:
  31     return "imaginary";
  32   case GoLexer::LIT_INTEGER:
  33     return "integer";
  34   case GoLexer::LIT_RUNE:
  35     return "rune";
  36   case GoLexer::LIT_STRING:
  37     return "string";
  38   default:
  39     return GoLexer::LookupToken(t);
  40   }
  41 }
  42 } // namespace
  43
  44 class GoParser::Rule {
  45 public:
  46   Rule(llvm::StringRef name, GoParser *p)
  47       : m_name(name), m_parser(p), m_pos(p->m_pos) {}
  48
  49   std::nullptr_t error() {
  50     if (!m_parser->m_failed) {
  51       // Set m_error in case this is the top level.
  52       if (m_parser->m_last_tok == GoLexer::TOK_INVALID)
  53         m_parser->m_error = m_parser->m_last;
  54       else
  55         m_parser->m_error = DescribeToken(m_parser->m_last_tok);
  56       // And set m_last in case it isn't.
  57       m_parser->m_last = m_name;
  58       m_parser->m_last_tok = GoLexer::TOK_INVALID;
  59       m_parser->m_pos = m_pos;
  60     }
  61     return nullptr;
  62   }
  63
  64 private:
  65   llvm::StringRef m_name;
  66   GoParser *m_parser;
  67   size_t m_pos;
  68 };
  69
  70 GoParser::GoParser(const char *src) : m_lexer(src), m_pos(0), m_failed(false) {}
  71
  72 GoASTStmt *GoParser::Statement() {
  73   Rule r("Statement", this);
  74   GoLexer::TokenType t = peek();
  75   GoASTStmt *ret = nullptr;
  76   switch (t) {
  77   case GoLexer::TOK_EOF:
  78   case GoLexer::OP_SEMICOLON:
  79   case GoLexer::OP_RPAREN:
  80   case GoLexer::OP_RBRACE:
  81   case GoLexer::TOK_INVALID:
  82     return EmptyStmt();
  83   case GoLexer::OP_LBRACE:
  84     return Block();
  85
  86   /*      TODO:
  87 case GoLexer::KEYWORD_GO:
  88   return GoStmt();
  89 case GoLexer::KEYWORD_RETURN:
  90   return ReturnStmt();
  91 case GoLexer::KEYWORD_BREAK:
  92 case GoLexer::KEYWORD_CONTINUE:
  93 case GoLexer::KEYWORD_GOTO:
  94 case GoLexer::KEYWORD_FALLTHROUGH:
  95   return BranchStmt();
  96 case GoLexer::KEYWORD_IF:
  97   return IfStmt();
  98 case GoLexer::KEYWORD_SWITCH:
  99   return SwitchStmt();
 100 case GoLexer::KEYWORD_SELECT:
 101   return SelectStmt();
 102 case GoLexer::KEYWORD_FOR:
 103   return ForStmt();
 104 case GoLexer::KEYWORD_DEFER:
 105   return DeferStmt();
 106 case GoLexer::KEYWORD_CONST:
 107 case GoLexer::KEYWORD_TYPE:
 108 case GoLexer::KEYWORD_VAR:
 109   return DeclStmt();
 110 case GoLexer::TOK_IDENTIFIER:
 111   if ((ret = LabeledStmt()) ||
 112       (ret = ShortVarDecl()))
 113   {
 114       return ret;
 115   }
 116 */
 117   default:
 118     break;
 119   }
 120   GoASTExpr *expr = Expression();
 121   if (expr == nullptr)
 122     return r.error();
 123   if (/*(ret = SendStmt(expr)) ||*/
 124       (ret = IncDecStmt(expr)) || (ret = Assignment(expr)) ||
 125       (ret = ExpressionStmt(expr))) {
 126     return ret;
 127   }
 128   delete expr;
 129   return r.error();
 130 }
 131
 132 GoASTStmt *GoParser::ExpressionStmt(GoASTExpr *e) {
 133   if (Semicolon())
 134     return new GoASTExprStmt(e);
 135   return nullptr;
 136 }
 137
 138 GoASTStmt *GoParser::IncDecStmt(GoASTExpr *e) {
 139   Rule r("IncDecStmt", this);
 140   if (match(GoLexer::OP_PLUS_PLUS))
 141     return Semicolon() ? new GoASTIncDecStmt(e, GoLexer::OP_PLUS_PLUS)
 142                        : r.error();
 143   if (match(GoLexer::OP_MINUS_MINUS))
 144     return Semicolon() ? new GoASTIncDecStmt(e, GoLexer::OP_MINUS_MINUS)
 145                        : r.error();
 146   return nullptr;
 147 }
 148
 149 GoASTStmt *GoParser::Assignment(lldb_private::GoASTExpr *e) {
 150   Rule r("Assignment", this);
 151   std::vector<std::unique_ptr<GoASTExpr>> lhs;
 152   for (GoASTExpr *l = MoreExpressionList(); l; l = MoreExpressionList())
 153     lhs.push_back(std::unique_ptr<GoASTExpr>(l));
 154   switch (peek()) {
 155   case GoLexer::OP_EQ:
 156   case GoLexer::OP_PLUS_EQ:
 157   case GoLexer::OP_MINUS_EQ:
 158   case GoLexer::OP_PIPE_EQ:
 159   case GoLexer::OP_CARET_EQ:
 160   case GoLexer::OP_STAR_EQ:
 161   case GoLexer::OP_SLASH_EQ:
 162   case GoLexer::OP_PERCENT_EQ:
 163   case GoLexer::OP_LSHIFT_EQ:
 164   case GoLexer::OP_RSHIFT_EQ:
 165   case GoLexer::OP_AMP_EQ:
 166   case GoLexer::OP_AMP_CARET_EQ:
 167     break;
 168   default:
 169     return r.error();
 170   }
 171   // We don't want to own e until we know this is an assignment.
 172   std::unique_ptr<GoASTAssignStmt> stmt(new GoASTAssignStmt(false));
 173   stmt->AddLhs(e);
 174   for (auto &l : lhs)
 175     stmt->AddLhs(l.release());
 176   for (GoASTExpr *r = Expression(); r; r = MoreExpressionList())
 177     stmt->AddRhs(r);
 178   if (!Semicolon() || stmt->NumRhs() == 0)
 179     return new GoASTBadStmt;
 180   return stmt.release();
 181 }
 182
 183 GoASTStmt *GoParser::EmptyStmt() {
 184   if (match(GoLexer::TOK_EOF))
 185     return nullptr;
 186   if (Semicolon())
 187     return new GoASTEmptyStmt;
 188   return nullptr;
 189 }
 190
 191 GoASTStmt *GoParser::GoStmt() {
 192   if (match(GoLexer::KEYWORD_GO)) {
 193     if (GoASTCallExpr *e =
 194             llvm::dyn_cast_or_null<GoASTCallExpr>(Expression())) {
 195       return FinishStmt(new GoASTGoStmt(e));
 196     }
 197     m_last = "call expression";
 198     m_failed = true;
 199     return new GoASTBadStmt();
 200   }
 201   return nullptr;
 202 }
 203
 204 GoASTStmt *GoParser::ReturnStmt() {
 205   if (match(GoLexer::KEYWORD_RETURN)) {
 206     std::unique_ptr<GoASTReturnStmt> r(new GoASTReturnStmt());
 207     for (GoASTExpr *e = Expression(); e; e = MoreExpressionList())
 208       r->AddResults(e);
 209     return FinishStmt(r.release());
 210   }
 211   return nullptr;
 212 }
 213
 214 GoASTStmt *GoParser::BranchStmt() {
 215   GoLexer::Token *tok;
 216   if ((tok = match(GoLexer::KEYWORD_BREAK)) ||
 217       (tok = match(GoLexer::KEYWORD_CONTINUE)) ||
 218       (tok = match(GoLexer::KEYWORD_GOTO))) {
 219     auto *e = Identifier();
 220     if (tok->m_type == GoLexer::KEYWORD_GOTO && !e)
 221       return syntaxerror();
 222     return FinishStmt(new GoASTBranchStmt(e, tok->m_type));
 223   }
 224   if ((tok = match(GoLexer::KEYWORD_FALLTHROUGH)))
 225     return FinishStmt(new GoASTBranchStmt(nullptr, tok->m_type));
 226
 227   return nullptr;
 228 }
 229
 230 GoASTIdent *GoParser::Identifier() {
 231   if (auto *tok = match(GoLexer::TOK_IDENTIFIER))
 232     return new GoASTIdent(*tok);
 233   return nullptr;
 234 }
 235
 236 GoASTExpr *GoParser::MoreExpressionList() {
 237   if (match(GoLexer::OP_COMMA)) {
 238     auto *e = Expression();
 239     if (!e)
 240       return syntaxerror();
 241     return e;
 242   }
 243   return nullptr;
 244 }
 245
 246 GoASTIdent *GoParser::MoreIdentifierList() {
 247   if (match(GoLexer::OP_COMMA)) {
 248     auto *i = Identifier();
 249     if (!i)
 250       return syntaxerror();
 251     return i;
 252   }
 253   return nullptr;
 254 }
 255
 256 GoASTExpr *GoParser::Expression() {
 257   Rule r("Expression", this);
 258   if (GoASTExpr *ret = OrExpr())
 259     return ret;
 260   return r.error();
 261 }
 262
 263 GoASTExpr *GoParser::UnaryExpr() {
 264   switch (peek()) {
 265   case GoLexer::OP_PLUS:
 266   case GoLexer::OP_MINUS:
 267   case GoLexer::OP_BANG:
 268   case GoLexer::OP_CARET:
 269   case GoLexer::OP_STAR:
 270   case GoLexer::OP_AMP:
 271   case GoLexer::OP_LT_MINUS: {
 272     const GoLexer::Token t = next();
 273     if (GoASTExpr *e = UnaryExpr()) {
 274       if (t.m_type == GoLexer::OP_STAR)
 275         return new GoASTStarExpr(e);
 276       else
 277         return new GoASTUnaryExpr(t.m_type, e);
 278     }
 279     return syntaxerror();
 280   }
 281   default:
 282     return PrimaryExpr();
 283   }
 284 }
 285
 286 GoASTExpr *GoParser::OrExpr() {
 287   std::unique_ptr<GoASTExpr> l(AndExpr());
 288   if (l) {
 289     while (match(GoLexer::OP_PIPE_PIPE)) {
 290       GoASTExpr *r = AndExpr();
 291       if (r)
 292         l.reset(new GoASTBinaryExpr(l.release(), r, GoLexer::OP_PIPE_PIPE));
 293       else
 294         return syntaxerror();
 295     }
 296     return l.release();
 297   }
 298   return nullptr;
 299 }
 300
 301 GoASTExpr *GoParser::AndExpr() {
 302   std::unique_ptr<GoASTExpr> l(RelExpr());
 303   if (l) {
 304     while (match(GoLexer::OP_AMP_AMP)) {
 305       GoASTExpr *r = RelExpr();
 306       if (r)
 307         l.reset(new GoASTBinaryExpr(l.release(), r, GoLexer::OP_AMP_AMP));
 308       else
 309         return syntaxerror();
 310     }
 311     return l.release();
 312   }
 313   return nullptr;
 314 }
 315
 316 GoASTExpr *GoParser::RelExpr() {
 317   std::unique_ptr<GoASTExpr> l(AddExpr());
 318   if (l) {
 319     for (GoLexer::Token *t;
 320          (t = match(GoLexer::OP_EQ_EQ)) || (t = match(GoLexer::OP_BANG_EQ)) ||
 321          (t = match(GoLexer::OP_LT)) || (t = match(GoLexer::OP_LT_EQ)) ||
 322          (t = match(GoLexer::OP_GT)) || (t = match(GoLexer::OP_GT_EQ));) {
 323       GoLexer::TokenType op = t->m_type;
 324       GoASTExpr *r = AddExpr();
 325       if (r)
 326         l.reset(new GoASTBinaryExpr(l.release(), r, op));
 327       else
 328         return syntaxerror();
 329     }
 330     return l.release();
 331   }
 332   return nullptr;
 333 }
 334
 335 GoASTExpr *GoParser::AddExpr() {
 336   std::unique_ptr<GoASTExpr> l(MulExpr());
 337   if (l) {
 338     for (GoLexer::Token *t;
 339          (t = match(GoLexer::OP_PLUS)) || (t = match(GoLexer::OP_MINUS)) ||
 340          (t = match(GoLexer::OP_PIPE)) || (t = match(GoLexer::OP_CARET));) {
 341       GoLexer::TokenType op = t->m_type;
 342       GoASTExpr *r = MulExpr();
 343       if (r)
 344         l.reset(new GoASTBinaryExpr(l.release(), r, op));
 345       else
 346         return syntaxerror();
 347     }
 348     return l.release();
 349   }
 350   return nullptr;
 351 }
 352
 353 GoASTExpr *GoParser::MulExpr() {
 354   std::unique_ptr<GoASTExpr> l(UnaryExpr());
 355   if (l) {
 356     for (GoLexer::Token *t;
 357          (t = match(GoLexer::OP_STAR)) || (t = match(GoLexer::OP_SLASH)) ||
 358          (t = match(GoLexer::OP_PERCENT)) || (t = match(GoLexer::OP_LSHIFT)) ||
 359          (t = match(GoLexer::OP_RSHIFT)) || (t = match(GoLexer::OP_AMP)) ||
 360          (t = match(GoLexer::OP_AMP_CARET));) {
 361       GoLexer::TokenType op = t->m_type;
 362       GoASTExpr *r = UnaryExpr();
 363       if (r)
 364         l.reset(new GoASTBinaryExpr(l.release(), r, op));
 365       else
 366         return syntaxerror();
 367     }
 368     return l.release();
 369   }
 370   return nullptr;
 371 }
 372
 373 GoASTExpr *GoParser::PrimaryExpr() {
 374   GoASTExpr *l;
 375   GoASTExpr *r;
 376   (l = Conversion()) || (l = Operand());
 377   if (!l)
 378     return nullptr;
 379   while ((r = Selector(l)) || (r = IndexOrSlice(l)) || (r = TypeAssertion(l)) ||
 380          (r = Arguments(l))) {
 381     l = r;
 382   }
 383   return l;
 384 }
 385
 386 GoASTExpr *GoParser::Operand() {
 387   GoLexer::Token *lit;
 388   if ((lit = match(GoLexer::LIT_INTEGER)) ||
 389       (lit = match(GoLexer::LIT_FLOAT)) ||
 390       (lit = match(GoLexer::LIT_IMAGINARY)) ||
 391       (lit = match(GoLexer::LIT_RUNE)) || (lit = match(GoLexer::LIT_STRING)))
 392     return new GoASTBasicLit(*lit);
 393   if (match(GoLexer::OP_LPAREN)) {
 394     GoASTExpr *e;
 395     if (!((e = Expression()) && match(GoLexer::OP_RPAREN)))
 396       return syntaxerror();
 397     return e;
 398   }
 399   // MethodExpr should be handled by Selector
 400   if (GoASTExpr *e = CompositeLit())
 401     return e;
 402   if (GoASTExpr *n = Name())
 403     return n;
 404   return FunctionLit();
 405 }
 406
 407 GoASTExpr *GoParser::FunctionLit() {
 408   if (!match(GoLexer::KEYWORD_FUNC))
 409     return nullptr;
 410   auto *sig = Signature();
 411   if (!sig)
 412     return syntaxerror();
 413   auto *body = Block();
 414   if (!body) {
 415     delete sig;
 416     return syntaxerror();
 417   }
 418   return new GoASTFuncLit(sig, body);
 419 }
 420
 421 GoASTBlockStmt *GoParser::Block() {
 422   if (!match(GoLexer::OP_LBRACE))
 423     return nullptr;
 424   std::unique_ptr<GoASTBlockStmt> block(new GoASTBlockStmt);
 425   for (auto *s = Statement(); s; s = Statement())
 426     block->AddList(s);
 427   if (!match(GoLexer::OP_RBRACE))
 428     return syntaxerror();
 429   return block.release();
 430 }
 431
 432 GoASTExpr *GoParser::CompositeLit() {
 433   Rule r("CompositeLit", this);
 434   GoASTExpr *type;
 435   (type = StructType()) || (type = ArrayOrSliceType(true)) ||
 436       (type = MapType()) || (type = Name());
 437   if (!type)
 438     return r.error();
 439   GoASTCompositeLit *lit = LiteralValue();
 440   if (!lit)
 441     return r.error();
 442   lit->SetType(type);
 443   return lit;
 444 }
 445
 446 GoASTCompositeLit *GoParser::LiteralValue() {
 447   if (!match(GoLexer::OP_LBRACE))
 448     return nullptr;
 449   std::unique_ptr<GoASTCompositeLit> lit(new GoASTCompositeLit);
 450   for (GoASTExpr *e = Element(); e; e = Element()) {
 451     lit->AddElts(e);
 452     if (!match(GoLexer::OP_COMMA))
 453       break;
 454   }
 455   if (!mustMatch(GoLexer::OP_RBRACE))
 456     return nullptr;
 457   return lit.release();
 458 }
 459
 460 GoASTExpr *GoParser::Element() {
 461   GoASTExpr *key;
 462   if (!((key = Expression()) || (key = LiteralValue())))
 463     return nullptr;
 464   if (!match(GoLexer::OP_COLON))
 465     return key;
 466   GoASTExpr *value;
 467   if ((value = Expression()) || (value = LiteralValue()))
 468     return new GoASTKeyValueExpr(key, value);
 469   delete key;
 470   return syntaxerror();
 471 }
 472
 473 GoASTExpr *GoParser::Selector(GoASTExpr *e) {
 474   Rule r("Selector", this);
 475   if (match(GoLexer::OP_DOT)) {
 476     if (auto *name = Identifier())
 477       return new GoASTSelectorExpr(e, name);
 478   }
 479   return r.error();
 480 }
 481
 482 GoASTExpr *GoParser::IndexOrSlice(GoASTExpr *e) {
 483   Rule r("IndexOrSlice", this);
 484   if (match(GoLexer::OP_LBRACK)) {
 485     std::unique_ptr<GoASTExpr> i1(Expression()), i2, i3;
 486     bool slice = false;
 487     if (match(GoLexer::OP_COLON)) {
 488       slice = true;
 489       i2.reset(Expression());
 490       if (i2 && match(GoLexer::OP_COLON)) {
 491         i3.reset(Expression());
 492         if (!i3)
 493           return syntaxerror();
 494       }
 495     }
 496     if (!(slice || i1))
 497       return syntaxerror();
 498     if (!mustMatch(GoLexer::OP_RBRACK))
 499       return nullptr;
 500     if (slice) {
 501       bool slice3 = i3.get();
 502       return new GoASTSliceExpr(e, i1.release(), i2.release(), i3.release(),
 503                                 slice3);
 504     }
 505     return new GoASTIndexExpr(e, i1.release());
 506   }
 507   return r.error();
 508 }
 509
 510 GoASTExpr *GoParser::TypeAssertion(GoASTExpr *e) {
 511   Rule r("TypeAssertion", this);
 512   if (match(GoLexer::OP_DOT) && match(GoLexer::OP_LPAREN)) {
 513     if (auto *t = Type()) {
 514       if (!mustMatch(GoLexer::OP_RPAREN))
 515         return nullptr;
 516       return new GoASTTypeAssertExpr(e, t);
 517     }
 518     return syntaxerror();
 519   }
 520   return r.error();
 521 }
 522
 523 GoASTExpr *GoParser::Arguments(GoASTExpr *e) {
 524   if (match(GoLexer::OP_LPAREN)) {
 525     std::unique_ptr<GoASTCallExpr> call(new GoASTCallExpr(false));
 526     GoASTExpr *arg;
 527     // ( ExpressionList | Type [ "," ExpressionList ] )
 528     for ((arg = Expression()) || (arg = Type()); arg;
 529          arg = MoreExpressionList()) {
 530       call->AddArgs(arg);
 531     }
 532     if (match(GoLexer::OP_DOTS))
 533       call->SetEllipsis(true);
 534
 535     // Eat trailing comma
 536     match(GoLexer::OP_COMMA);
 537
 538     if (!mustMatch(GoLexer::OP_RPAREN))
 539       return nullptr;
 540     call->SetFun(e);
 541     return call.release();
 542   }
 543   return nullptr;
 544 }
 545
 546 GoASTExpr *GoParser::Conversion() {
 547   Rule r("Conversion", this);
 548   if (GoASTExpr *t = Type2()) {
 549     if (match(GoLexer::OP_LPAREN)) {
 550       GoASTExpr *v = Expression();
 551       if (!v)
 552         return syntaxerror();
 553       match(GoLexer::OP_COMMA);
 554       if (!mustMatch(GoLexer::OP_RPAREN))
 555         return r.error();
 556       GoASTCallExpr *call = new GoASTCallExpr(false);
 557       call->SetFun(t);
 558       call->AddArgs(v);
 559       return call;
 560     }
 561   }
 562   return r.error();
 563 }
 564
 565 GoASTExpr *GoParser::Type2() {
 566   switch (peek()) {
 567   case GoLexer::OP_LBRACK:
 568     return ArrayOrSliceType(false);
 569   case GoLexer::KEYWORD_STRUCT:
 570     return StructType();
 571   case GoLexer::KEYWORD_FUNC:
 572     return FunctionType();
 573   case GoLexer::KEYWORD_INTERFACE:
 574     return InterfaceType();
 575   case GoLexer::KEYWORD_MAP:
 576     return MapType();
 577   case GoLexer::KEYWORD_CHAN:
 578     return ChanType2();
 579   default:
 580     return nullptr;
 581   }
 582 }
 583
 584 GoASTExpr *GoParser::ArrayOrSliceType(bool allowEllipsis) {
 585   Rule r("ArrayType", this);
 586   if (match(GoLexer::OP_LBRACK)) {
 587     std::unique_ptr<GoASTExpr> len;
 588     if (allowEllipsis && match(GoLexer::OP_DOTS)) {
 589       len.reset(new GoASTEllipsis(nullptr));
 590     } else {
 591       len.reset(Expression());
 592     }
 593
 594     if (!match(GoLexer::OP_RBRACK))
 595       return r.error();
 596     GoASTExpr *elem = Type();
 597     if (!elem)
 598       return syntaxerror();
 599     return new GoASTArrayType(len.release(), elem);
 600   }
 601   return r.error();
 602 }
 603
 604 GoASTExpr *GoParser::StructType() {
 605   if (!(match(GoLexer::KEYWORD_STRUCT) && mustMatch(GoLexer::OP_LBRACE)))
 606     return nullptr;
 607   std::unique_ptr<GoASTFieldList> fields(new GoASTFieldList);
 608   while (auto *field = FieldDecl())
 609     fields->AddList(field);
 610   if (!mustMatch(GoLexer::OP_RBRACE))
 611     return nullptr;
 612   return new GoASTStructType(fields.release());
 613 }
 614
 615 GoASTField *GoParser::FieldDecl() {
 616   std::unique_ptr<GoASTField> f(new GoASTField);
 617   GoASTExpr *t = FieldNamesAndType(f.get());
 618   if (!t)
 619     t = AnonymousFieldType();
 620   if (!t)
 621     return nullptr;
 622
 623   if (auto *tok = match(GoLexer::LIT_STRING))
 624     f->SetTag(new GoASTBasicLit(*tok));
 625   if (!Semicolon())
 626     return syntaxerror();
 627   return f.release();
 628 }
 629
 630 GoASTExpr *GoParser::FieldNamesAndType(GoASTField *field) {
 631   Rule r("FieldNames", this);
 632   for (auto *id = Identifier(); id; id = MoreIdentifierList())
 633     field->AddNames(id);
 634   if (m_failed)
 635     return nullptr;
 636   GoASTExpr *t = Type();
 637   if (t)
 638     return t;
 639   return r.error();
 640 }
 641
 642 GoASTExpr *GoParser::AnonymousFieldType() {
 643   bool pointer = match(GoLexer::OP_STAR);
 644   GoASTExpr *t = Type();
 645   if (!t)
 646     return nullptr;
 647   if (pointer)
 648     return new GoASTStarExpr(t);
 649   return t;
 650 }
 651
 652 GoASTExpr *GoParser::FunctionType() {
 653   if (!match(GoLexer::KEYWORD_FUNC))
 654     return nullptr;
 655   return Signature();
 656 }
 657
 658 GoASTFuncType *GoParser::Signature() {
 659   auto *params = Params();
 660   if (!params)
 661     return syntaxerror();
 662   auto *result = Params();
 663   if (!result) {
 664     if (auto *t = Type()) {
 665       result = new GoASTFieldList;
 666       auto *f = new GoASTField;
 667       f->SetType(t);
 668       result->AddList(f);
 669     }
 670   }
 671   return new GoASTFuncType(params, result);
 672 }
 673
 674 GoASTFieldList *GoParser::Params() {
 675   if (!match(GoLexer::OP_LPAREN))
 676     return nullptr;
 677   std::unique_ptr<GoASTFieldList> l(new GoASTFieldList);
 678   while (GoASTField *p = ParamDecl()) {
 679     l->AddList(p);
 680     if (!match(GoLexer::OP_COMMA))
 681       break;
 682   }
 683   if (!mustMatch(GoLexer::OP_RPAREN))
 684     return nullptr;
 685   return l.release();
 686 }
 687
 688 GoASTField *GoParser::ParamDecl() {
 689   std::unique_ptr<GoASTField> field(new GoASTField);
 690   GoASTIdent *id = Identifier();
 691   if (id) {
 692     // Try `IdentifierList [ "..." ] Type`.
 693     // If that fails, backtrack and try `[ "..." ] Type`.
 694     Rule r("NamedParam", this);
 695     for (; id; id = MoreIdentifierList())
 696       field->AddNames(id);
 697     GoASTExpr *t = ParamType();
 698     if (t) {
 699       field->SetType(t);
 700       return field.release();
 701     }
 702     field.reset(new GoASTField);
 703     r.error();
 704   }
 705   GoASTExpr *t = ParamType();
 706   if (t) {
 707     field->SetType(t);
 708     return field.release();
 709   }
 710   return nullptr;
 711 }
 712
 713 GoASTExpr *GoParser::ParamType() {
 714   bool dots = match(GoLexer::OP_DOTS);
 715   GoASTExpr *t = Type();
 716   if (!dots)
 717     return t;
 718   if (!t)
 719     return syntaxerror();
 720   return new GoASTEllipsis(t);
 721 }
 722
 723 GoASTExpr *GoParser::InterfaceType() {
 724   if (!match(GoLexer::KEYWORD_INTERFACE) || !mustMatch(GoLexer::OP_LBRACE))
 725     return nullptr;
 726   std::unique_ptr<GoASTFieldList> methods(new GoASTFieldList);
 727   while (true) {
 728     Rule r("MethodSpec", this);
 729     // ( identifier Signature | TypeName ) ;
 730     std::unique_ptr<GoASTIdent> id(Identifier());
 731     if (!id)
 732       break;
 733     GoASTExpr *type = Signature();
 734     if (!type) {
 735       r.error();
 736       id.reset();
 737       type = Name();
 738     }
 739     if (!Semicolon())
 740       return syntaxerror();
 741     auto *f = new GoASTField;
 742     if (id)
 743       f->AddNames(id.release());
 744     f->SetType(type);
 745     methods->AddList(f);
 746   }
 747   if (!mustMatch(GoLexer::OP_RBRACE))
 748     return nullptr;
 749   return new GoASTInterfaceType(methods.release());
 750 }
 751
 752 GoASTExpr *GoParser::MapType() {
 753   if (!(match(GoLexer::KEYWORD_MAP) && mustMatch(GoLexer::OP_LBRACK)))
 754     return nullptr;
 755   std::unique_ptr<GoASTExpr> key(Type());
 756   if (!key)
 757     return syntaxerror();
 758   if (!mustMatch(GoLexer::OP_RBRACK))
 759     return nullptr;
 760   auto *elem = Type();
 761   if (!elem)
 762     return syntaxerror();
 763   return new GoASTMapType(key.release(), elem);
 764 }
 765
 766 GoASTExpr *GoParser::ChanType() {
 767   Rule r("chan", this);
 768   if (match(GoLexer::OP_LT_MINUS)) {
 769     if (match(GoLexer::KEYWORD_CHAN)) {
 770       auto *elem = Type();
 771       if (!elem)
 772         return syntaxerror();
 773       return new GoASTChanType(GoASTNode::eChanRecv, elem);
 774     }
 775     return r.error();
 776   }
 777   return ChanType2();
 778 }
 779
 780 GoASTExpr *GoParser::ChanType2() {
 781   if (!match(GoLexer::KEYWORD_CHAN))
 782     return nullptr;
 783   auto dir = GoASTNode::eChanBidir;
 784   if (match(GoLexer::OP_LT_MINUS))
 785     dir = GoASTNode::eChanSend;
 786   auto *elem = Type();
 787   if (!elem)
 788     return syntaxerror();
 789   return new GoASTChanType(dir, elem);
 790 }
 791
 792 GoASTExpr *GoParser::Type() {
 793   if (GoASTExpr *t = Type2())
 794     return t;
 795   if (GoASTExpr *t = Name())
 796     return t;
 797   if (GoASTExpr *t = ChanType())
 798     return t;
 799   if (match(GoLexer::OP_STAR)) {
 800     GoASTExpr *t = Type();
 801     if (!t)
 802       return syntaxerror();
 803     return new GoASTStarExpr(t);
 804   }
 805   if (match(GoLexer::OP_LPAREN)) {
 806     std::unique_ptr<GoASTExpr> t(Type());
 807     if (!t || !match(GoLexer::OP_RPAREN))
 808       return syntaxerror();
 809     return t.release();
 810   }
 811   return nullptr;
 812 }
 813
 814 bool GoParser::Semicolon() {
 815   if (match(GoLexer::OP_SEMICOLON))
 816     return true;
 817   switch (peek()) {
 818   case GoLexer::OP_RPAREN:
 819   case GoLexer::OP_RBRACE:
 820   case GoLexer::TOK_EOF:
 821     return true;
 822   default:
 823     return false;
 824   }
 825 }
 826
 827 GoASTExpr *GoParser::Name() {
 828   if (auto *id = Identifier()) {
 829     if (GoASTExpr *qual = QualifiedIdent(id))
 830       return qual;
 831     return id;
 832   }
 833   return nullptr;
 834 }
 835
 836 GoASTExpr *GoParser::QualifiedIdent(lldb_private::GoASTIdent *p) {
 837   Rule r("QualifiedIdent", this);
 838   llvm::SmallString<32> path(p->GetName().m_value);
 839   GoLexer::Token *next;
 840   bool have_slashes = false;
 841   // LLDB extension: support full/package/path.name
 842   while (match(GoLexer::OP_SLASH) && (next = match(GoLexer::TOK_IDENTIFIER))) {
 843     have_slashes = true;
 844     path.append("/");
 845     path.append(next->m_value);
 846   }
 847   if (match(GoLexer::OP_DOT)) {
 848     auto *name = Identifier();
 849     if (name) {
 850       if (have_slashes) {
 851         p->SetName(GoLexer::Token(GoLexer::TOK_IDENTIFIER, CopyString(path)));
 852       }
 853       return new GoASTSelectorExpr(p, name);
 854     }
 855   }
 856   return r.error();
 857 }
 858
 859 llvm::StringRef GoParser::CopyString(llvm::StringRef s) {
 860   return m_strings.insert(std::make_pair(s, 'x')).first->getKey();
 861 }
 862
 863 void GoParser::GetError(Error &error) {
 864   llvm::StringRef want;
 865   if (m_failed)
 866     want =
 867         m_last_tok == GoLexer::TOK_INVALID ? DescribeToken(m_last_tok) : m_last;
 868   else
 869     want = m_error;
 870   size_t len = m_lexer.BytesRemaining();
 871   if (len > 10)
 872     len = 10;
 873   llvm::StringRef got;
 874   if (len == 0)
 875     got = "<eof>";
 876   else
 877     got = m_lexer.GetString(len);
 878   error.SetErrorStringWithFormat("Syntax error: expected %s before '%s'.",
 879                                  want.str().c_str(), got.str().c_str());
 880 }