lib/TableGen/TGPreprocessor.cpp

   1 //===- TGPreprocessor.cpp - Preprocessor for TableGen ---------------------===//
   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 // Implement the Preprocessor for TableGen.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "TGPreprocessor.h"
  15 #include "llvm/ADT/Twine.h"
  16 #include "llvm/Support/MemoryBuffer.h"
  17 #include "llvm/Support/SourceMgr.h"
  18 #include "llvm/Support/ToolOutputFile.h"
  19 #include "llvm/TableGen/Error.h"
  20 #include <map>
  21 #include <string>
  22 #include <cctype>
  23 #include <cstdio>
  24 #include <cstdlib>
  25 #include <cstring>
  26
  27 namespace llvm {
  28 typedef std::map<std::string, std::string> TGPPEnvironment;
  29
  30 enum TGPPTokenKind {
  31   tgpptoken_symbol,
  32   tgpptoken_literal,
  33   tgpptoken_newline,
  34   tgpptoken_error,
  35   tgpptoken_end
  36 };
  37
  38 enum TGPPRecordKind {
  39   tgpprecord_for,
  40   tgpprecord_variable,
  41   tgpprecord_literal
  42 };
  43
  44 enum TGPPRangeKind {
  45   tgpprange_list,
  46   tgpprange_sequence
  47 };
  48
  49 bool MatchSymbol(TGPPTokenKind Kind,
  50                  const char *BeginOfToken, const char *EndOfToken,
  51                  char Symbol);
  52
  53 bool MatchSymbol(TGPPTokenKind Kind,
  54                  const char *BeginOfToken, const char *EndOfToken,
  55                  const char *Symbol);
  56
  57 bool MatchIdNum(TGPPTokenKind Kind,
  58                 const char *BeginOfToken, const char *EndOfToken);
  59
  60 bool MatchIdentifier(TGPPTokenKind Kind,
  61                      const char *BeginOfToken, const char *EndOfToken);
  62
  63 bool MatchNumber(TGPPTokenKind Kind,
  64                  const char *BeginOfToken, const char *EndOfToken,
  65                  long int *Val);
  66
  67 class TGPPLexer {
  68   const MemoryBuffer *CurBuf;
  69   const char *CurPtr;
  70   bool IsInsideMacroStatement, WasEndOfLine;
  71
  72   bool IsEndOfBuffer(const char *Ptr) const {
  73     return (!*Ptr && Ptr == CurBuf->getBufferEnd());
  74   }
  75
  76   bool IsNewLine() {
  77     if (*CurPtr == '\r' || *CurPtr == '\n') {
  78       if ((CurPtr[1] == '\r' || CurPtr[1] == '\n') && CurPtr[0] != CurPtr[1])
  79         ++CurPtr;
  80       return true;
  81     }
  82     return false;
  83   }
  84
  85   bool MatchPrefix(const char *Prefix, const char *Ptr) const {
  86     while (*Ptr == ' ' || *Ptr == '\t')
  87       ++Ptr;
  88     return !strncmp(Prefix, Ptr, strlen(Prefix));
  89   }
  90 public:
  91   TGPPLexer(const SourceMgr &SM)
  92     : CurBuf(SM.getMemoryBuffer(0)),
  93       CurPtr(CurBuf->getBufferStart()),
  94       IsInsideMacroStatement(false),
  95       WasEndOfLine(true) {
  96   }
  97
  98   TGPPTokenKind NextToken(const char **BeginOfToken, const char **EndOfToken);
  99 };
 100
 101 // preprocessor records
 102 class TGPPRecord {
 103   TGPPRecordKind Kind;
 104
 105   // tgpprecord_for
 106   std::vector<std::string> IndexVars;
 107   std::vector<TGPPRange> IndexRanges;
 108   TGPPRecords LoopBody;
 109
 110   // tgpprecord_variable, tgpprecord_literal
 111   std::string Str;
 112
 113   bool EvaluateFor(const TGPPEnvironment &Env, raw_fd_ostream &OS) const;
 114
 115   bool EvaluateVariable(const TGPPEnvironment &Env, raw_fd_ostream &OS) const {
 116     TGPPEnvironment::const_iterator it_val = Env.find(Str);
 117     if (it_val == Env.end()) {
 118       PrintError("Var is not bound to any value: " + Str);
 119       return true;
 120     }
 121     OS << it_val->second;
 122     return false;
 123   }
 124
 125   bool EvaluateLiteral(const TGPPEnvironment &Env, raw_fd_ostream &OS) const {
 126     OS << Str;
 127     return false;
 128   }
 129
 130 public:
 131   TGPPRecord(TGPPRecordKind K) : Kind(K) {}
 132   TGPPRecord(TGPPRecordKind K, const std::string &S) : Kind(K), Str(S) {}
 133
 134   TGPPRecords *GetLoopBody() { return &LoopBody; }
 135
 136   void AppendIndex(const std::string &V, const TGPPRange &R) {
 137     IndexVars.push_back(V);
 138     IndexRanges.push_back(R);
 139   }
 140
 141   bool Evaluate(const TGPPEnvironment &Env, raw_fd_ostream &OS) const;
 142 };
 143
 144 class TGPPRange {
 145   TGPPRangeKind Kind;
 146
 147   // tgpprange_list
 148   std::vector<std::string> Vals;
 149
 150   // tgpprange_sequence
 151   long int From, To;
 152
 153 public:
 154   TGPPRange() : Kind(tgpprange_list) {}
 155   TGPPRange(long int F, long int T)
 156     : Kind(tgpprange_sequence), From(F), To(T) {}
 157
 158   size_t size() const {
 159     if (Kind == tgpprange_list)
 160       return Vals.size();
 161     else
 162       return To - From + 1;
 163   }
 164
 165   std::string at(size_t i) const {
 166     if (Kind == tgpprange_list)
 167       return Vals.at(i);
 168     else {
 169       char buf[32];
 170       snprintf(buf, sizeof(buf), "%ld", From + (long int)i);
 171       return std::string(buf);
 172     }
 173   }
 174
 175   void push_back(const std::string &S) {
 176     if (Kind == tgpprange_list)
 177       Vals.push_back(S);
 178   }
 179 };
 180 } // namespace llvm
 181
 182 using namespace llvm;
 183
 184 bool llvm::MatchSymbol(TGPPTokenKind Kind,
 185                        const char *BeginOfToken, const char *EndOfToken,
 186                        char Symbol) {
 187   return Kind == tgpptoken_symbol &&
 188          BeginOfToken + 1 == EndOfToken &&
 189          Symbol == *BeginOfToken;
 190 }
 191
 192 bool llvm::MatchSymbol(TGPPTokenKind Kind,
 193                        const char *BeginOfToken, const char *EndOfToken,
 194                        const char *Symbol) {
 195   return Kind == tgpptoken_symbol &&
 196          BeginOfToken + strlen(Symbol) == EndOfToken &&
 197          !strncmp(Symbol, BeginOfToken, EndOfToken - BeginOfToken);
 198 }
 199
 200 bool llvm::MatchIdNum(TGPPTokenKind Kind,
 201                       const char *BeginOfToken, const char *EndOfToken) {
 202   if (Kind != tgpptoken_symbol)
 203     return false;
 204   for (const char *i = BeginOfToken; i != EndOfToken; ++i)
 205     if (*i != '_' && !isalnum(*i))
 206       return false;
 207   return true;
 208 }
 209
 210 bool llvm::MatchIdentifier(TGPPTokenKind Kind,
 211                            const char *BeginOfToken, const char *EndOfToken) {
 212   if (Kind != tgpptoken_symbol)
 213     return false;
 214
 215   const char *i = BeginOfToken;
 216   if (*i != '_' && !isalpha(*i))
 217     return false;
 218   for (++i; i != EndOfToken; ++i)
 219     if (*i != '_' && !isalnum(*i))
 220       return false;
 221
 222   return true;
 223 }
 224
 225 bool llvm::MatchNumber(TGPPTokenKind Kind,
 226                        const char *BeginOfToken, const char *EndOfToken,
 227                        long int *Val) {
 228   if (Kind != tgpptoken_symbol)
 229     return false;
 230   char *e;
 231   *Val = strtol(BeginOfToken, &e, 10);
 232   return e == EndOfToken;
 233 }
 234
 235 TGPPTokenKind TGPPLexer::
 236 NextToken(const char **BeginOfToken, const char **EndOfToken) {
 237   bool IsBeginOfLine = WasEndOfLine;
 238   WasEndOfLine = false;
 239
 240   if (IsEndOfBuffer(CurPtr))
 241     return tgpptoken_end;
 242
 243   else if (IsInsideMacroStatement) {
 244     while (*CurPtr == ' ' || *CurPtr == '\t') // trim space, if any
 245       ++CurPtr;
 246
 247     const char *BeginOfSymbol = CurPtr;
 248
 249     if (IsNewLine()) {
 250       ++CurPtr;
 251       IsInsideMacroStatement = false;
 252       WasEndOfLine = true;
 253       return tgpptoken_newline;
 254     }
 255
 256     else if (*CurPtr == '[' || *CurPtr == ']' ||
 257              *CurPtr == '(' || *CurPtr == ')' ||
 258              *CurPtr == ',' || *CurPtr == '=') {
 259       *BeginOfToken = BeginOfSymbol;
 260       *EndOfToken = ++CurPtr;
 261       return tgpptoken_symbol;
 262     }
 263
 264     else if (*CurPtr == '_' || isalpha(*CurPtr)) {
 265       ++CurPtr;
 266       while (*CurPtr == '_' || isalnum(*CurPtr))
 267         ++CurPtr;
 268       *BeginOfToken = BeginOfSymbol;
 269       *EndOfToken = CurPtr;
 270       return tgpptoken_symbol;
 271     }
 272
 273     else if (*CurPtr == '+' || *CurPtr == '-' || isdigit(*CurPtr)) {
 274       ++CurPtr;
 275       while (isdigit(*CurPtr))
 276         ++CurPtr;
 277       *BeginOfToken = BeginOfSymbol;
 278       *EndOfToken = CurPtr;
 279       return tgpptoken_symbol;
 280     }
 281
 282     else {
 283       PrintError(BeginOfSymbol, "Unrecognizable token");
 284       return tgpptoken_error;
 285     }
 286   }
 287
 288   else if (*CurPtr == '#') {
 289     if (IsBeginOfLine &&
 290         (MatchPrefix("for", CurPtr + 1) ||
 291          MatchPrefix("end", CurPtr + 1))) {
 292       ++CurPtr;
 293       IsInsideMacroStatement = true;
 294       return NextToken(BeginOfToken, EndOfToken);
 295     }
 296
 297     // special token #"# is translate to literal "
 298     else if (CurPtr[1] == '"' && CurPtr[2] == '#') {
 299       *BeginOfToken = ++CurPtr;
 300       *EndOfToken = ++CurPtr;
 301       ++CurPtr;
 302       return tgpptoken_literal;
 303     }
 304
 305     else {
 306       const char *BeginOfVar = ++CurPtr; // trim '#'
 307       if (*CurPtr != '_' && !isalpha(*CurPtr)) {
 308         PrintError(BeginOfVar, "Variable must start with [_A-Za-z]: ");
 309         return tgpptoken_error;
 310       }
 311       while (*CurPtr == '_' || isalnum(*CurPtr))
 312         ++CurPtr;
 313       if (*CurPtr != '#') {
 314         PrintError(BeginOfVar, "Variable must end with #");
 315         return tgpptoken_error;
 316       }
 317       *BeginOfToken = BeginOfVar;
 318       *EndOfToken = CurPtr++; // trim '#'
 319       return tgpptoken_symbol;
 320     }
 321   }
 322
 323   const char *BeginOfLiteral = CurPtr;
 324   int CCommentLevel = 0;
 325   bool BCPLComment = false;
 326   bool StringLiteral = false;
 327   for (; !IsEndOfBuffer(CurPtr); ++CurPtr) {
 328     if (CCommentLevel > 0) {
 329       if (CurPtr[0] == '/' && CurPtr[1] == '*') {
 330         ++CurPtr;
 331         ++CCommentLevel;
 332       } else if (CurPtr[0] == '*' && CurPtr[1] == '/') {
 333         ++CurPtr;
 334         --CCommentLevel;
 335       } else if (IsNewLine())
 336         WasEndOfLine = true;
 337     }
 338
 339     else if (BCPLComment) {
 340       if (IsNewLine()) {
 341         WasEndOfLine = true;
 342         BCPLComment = false;
 343       }
 344     }
 345
 346     else if (StringLiteral) {
 347       // no string escape sequence in TableGen?
 348       if (*CurPtr == '"')
 349         StringLiteral = false;
 350     }
 351
 352     else if (CurPtr[0] == '/' && CurPtr[1] == '*') {
 353       ++CurPtr;
 354       ++CCommentLevel;
 355     }
 356
 357     else if (CurPtr[0] == '/' && CurPtr[1] == '/') {
 358       ++CurPtr;
 359       BCPLComment = true;
 360     }
 361
 362     else if (*CurPtr == '"')
 363       StringLiteral = true;
 364
 365     else if (IsNewLine()) {
 366       ++CurPtr;
 367       WasEndOfLine = true;
 368       break;
 369     }
 370
 371     else if (*CurPtr == '#')
 372       break;
 373   }
 374
 375   *BeginOfToken = BeginOfLiteral;
 376   *EndOfToken = CurPtr;
 377   return tgpptoken_literal;
 378 }
 379
 380 bool TGPPRecord::
 381 EvaluateFor(const TGPPEnvironment &Env, raw_fd_ostream &OS) const {
 382   std::vector<TGPPRange>::const_iterator ri, re;
 383
 384   // calculate the min size
 385   ri = IndexRanges.begin();
 386   re = IndexRanges.begin();
 387   size_t n = ri->size();
 388   for (; ri != re; ++ri) {
 389     size_t m = ri->size();
 390     if (m < n)
 391       n = m;
 392   }
 393
 394   for (size_t which_val = 0; which_val < n; ++which_val) {
 395     // construct nested environment
 396     TGPPEnvironment NestedEnv(Env);
 397     std::vector<std::string>::const_iterator vi = IndexVars.begin();
 398     for (ri = IndexRanges.begin(), re = IndexRanges.end();
 399         ri != re; ++vi, ++ri) {
 400       NestedEnv.insert(std::make_pair(*vi, ri->at(which_val)));
 401     }
 402     // evalute loop body
 403     for (TGPPRecords::const_iterator i = LoopBody.begin(), e = LoopBody.end();
 404         i != e; ++i)
 405       if (i->Evaluate(NestedEnv, OS))
 406         return true;
 407   }
 408
 409   return false;
 410 }
 411
 412 bool TGPPRecord::
 413 Evaluate(const TGPPEnvironment &Env, raw_fd_ostream &OS) const {
 414   switch (Kind) {
 415   case tgpprecord_for:
 416     return EvaluateFor(Env, OS);
 417   case tgpprecord_variable:
 418     return EvaluateVariable(Env, OS);
 419   case tgpprecord_literal:
 420     return EvaluateLiteral(Env, OS);
 421   default:
 422     PrintError("Unknown kind of record: " + Kind);
 423     return true;
 424   }
 425   return false;
 426 }
 427
 428 bool TGPreprocessor::ParseBlock(bool TopLevel) {
 429   TGPPTokenKind Kind;
 430   const char *BeginOfToken, *EndOfToken;
 431   while ((Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken)) !=
 432          tgpptoken_end) {
 433     std::string Symbol(BeginOfToken, EndOfToken);
 434     switch (Kind) {
 435     case tgpptoken_symbol:
 436       if (Symbol == "for") {
 437         if (ParseForLoop())
 438           return true;
 439       } else if (Symbol == "end") {
 440         if (TopLevel) {
 441           PrintError(BeginOfToken, "No block to end here");
 442           return true;
 443         }
 444         if ((Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken)) !=
 445             tgpptoken_newline) {
 446           PrintError(BeginOfToken, "Tokens after #end");
 447           return true;
 448         }
 449         return false;
 450       } else if (Symbol == "NAME") {
 451         // treat '#NAME#' as a literal
 452         CurRecords->push_back(
 453             TGPPRecord(tgpprecord_literal,
 454                        std::string("#NAME#")));
 455       } else {
 456         CurRecords->push_back(
 457             TGPPRecord(tgpprecord_variable,
 458                        std::string(BeginOfToken, EndOfToken)));
 459       }
 460       break;
 461     case tgpptoken_literal:
 462       CurRecords->push_back(
 463           TGPPRecord(tgpprecord_literal,
 464                      std::string(BeginOfToken, EndOfToken)));
 465       break;
 466     default:
 467       return true;
 468     }
 469   }
 470   return false;
 471 }
 472
 473 bool TGPreprocessor::ParseForLoop() {
 474   TGPPRecord ForLoopRecord(tgpprecord_for);
 475
 476   for (;;) {
 477     TGPPTokenKind Kind;
 478     const char *BeginOfToken, *EndOfToken;
 479
 480     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 481     if (!MatchIdentifier(Kind, BeginOfToken, EndOfToken)) {
 482       PrintError(BeginOfToken, "Not an identifier");
 483       return true;
 484     }
 485     std::string IndexVar(BeginOfToken, EndOfToken);
 486
 487     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 488     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, '=')) {
 489       PrintError(BeginOfToken, "Need a '=' here");
 490       return true;
 491     }
 492
 493     TGPPRange Range;
 494     if (ParseRange(&Range))
 495       return true;
 496     ForLoopRecord.AppendIndex(IndexVar, Range);
 497
 498     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 499     if (Kind == tgpptoken_newline)
 500       break;
 501     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ',')) {
 502       PrintError(BeginOfToken, "Need a ',' here");
 503       return true;
 504     }
 505   }
 506
 507   // open a new level
 508   TGPPRecords *LastCurRecords = CurRecords;
 509   CurRecords = ForLoopRecord.GetLoopBody();
 510
 511   if (ParseBlock(false))
 512     return true;
 513
 514   CurRecords = LastCurRecords;
 515   CurRecords->push_back(ForLoopRecord);
 516   return false;
 517 }
 518
 519 bool TGPreprocessor::ParseRange(TGPPRange *Range) {
 520   TGPPTokenKind Kind;
 521   const char *BeginOfToken, *EndOfToken;
 522
 523   Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 524
 525   if (MatchSymbol(Kind, BeginOfToken, EndOfToken, '[')) {
 526     for (;;) {
 527       Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 528       if (!MatchIdNum(Kind, BeginOfToken, EndOfToken)) {
 529         PrintError(BeginOfToken, "Need a identifier or a number here");
 530         return true;
 531       }
 532       Range->push_back(std::string(BeginOfToken, EndOfToken));
 533
 534       Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 535       if (MatchSymbol(Kind, BeginOfToken, EndOfToken, ']'))
 536         break;
 537       if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ',')) {
 538         PrintError(BeginOfToken, "Need a comma here");
 539         return true;
 540       }
 541     }
 542     return false;
 543   }
 544
 545   else if (MatchSymbol(Kind, BeginOfToken, EndOfToken, "sequence")) {
 546     long int from, to;
 547
 548     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 549     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, '(')) {
 550       PrintError(BeginOfToken, "Need a left parentheses here");
 551       return true;
 552     }
 553
 554     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 555     if (!MatchNumber(Kind, BeginOfToken, EndOfToken, &from)) {
 556       PrintError(BeginOfToken, "Not a number");
 557       return true;
 558     }
 559
 560     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 561     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ',')) {
 562       PrintError(BeginOfToken, "Need a comma here");
 563       return true;
 564     }
 565
 566     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 567     if (!MatchNumber(Kind, BeginOfToken, EndOfToken, &to)) {
 568       PrintError(BeginOfToken, "Not a number");
 569       return true;
 570     }
 571
 572     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 573     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ')')) {
 574       PrintError(BeginOfToken, "Need a right parentheses here");
 575       return true;
 576     }
 577
 578     *Range = TGPPRange(from, to);
 579     return false;
 580   }
 581
 582   PrintError(BeginOfToken, "illegal range of loop index");
 583   return true;
 584 }
 585
 586 bool TGPreprocessor::PreprocessFile() {
 587   TGPPLexer TheLexer(SrcMgr);
 588   TGPPRecords TopLevelRecords;
 589
 590   Lexer = &TheLexer;
 591   CurRecords = &TopLevelRecords;
 592   if (ParseBlock(true))
 593     return true;
 594
 595   TGPPEnvironment Env;
 596   for (TGPPRecords::const_iterator i = TopLevelRecords.begin(),
 597                                    e = TopLevelRecords.end();
 598       i != e; ++i)
 599     if (i->Evaluate(Env, Out.os()))
 600       return true;
 601
 602   return false;
 603 }