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       std::string Result;
 170       raw_string_ostream Tmp(Result);
 171       Tmp << (From + (long int)i);
 172       return Tmp.str();
 173     }
 174   }
 175
 176   void push_back(const std::string &S) {
 177     if (Kind == tgpprange_list)
 178       Vals.push_back(S);
 179   }
 180 };
 181 } // namespace llvm
 182
 183 using namespace llvm;
 184
 185 bool llvm::MatchSymbol(TGPPTokenKind Kind,
 186                        const char *BeginOfToken, const char *EndOfToken,
 187                        char Symbol) {
 188   return Kind == tgpptoken_symbol &&
 189          BeginOfToken + 1 == EndOfToken &&
 190          Symbol == *BeginOfToken;
 191 }
 192
 193 bool llvm::MatchSymbol(TGPPTokenKind Kind,
 194                        const char *BeginOfToken, const char *EndOfToken,
 195                        const char *Symbol) {
 196   return Kind == tgpptoken_symbol &&
 197          BeginOfToken + strlen(Symbol) == EndOfToken &&
 198          !strncmp(Symbol, BeginOfToken, EndOfToken - BeginOfToken);
 199 }
 200
 201 bool llvm::MatchIdNum(TGPPTokenKind Kind,
 202                       const char *BeginOfToken, const char *EndOfToken) {
 203   if (Kind != tgpptoken_symbol)
 204     return false;
 205   for (const char *i = BeginOfToken; i != EndOfToken; ++i)
 206     if (*i != '_' && !isalnum(*i))
 207       return false;
 208   return true;
 209 }
 210
 211 bool llvm::MatchIdentifier(TGPPTokenKind Kind,
 212                            const char *BeginOfToken, const char *EndOfToken) {
 213   if (Kind != tgpptoken_symbol)
 214     return false;
 215
 216   const char *i = BeginOfToken;
 217   if (*i != '_' && !isalpha(*i))
 218     return false;
 219   for (++i; i != EndOfToken; ++i)
 220     if (*i != '_' && !isalnum(*i))
 221       return false;
 222
 223   return true;
 224 }
 225
 226 bool llvm::MatchNumber(TGPPTokenKind Kind,
 227                        const char *BeginOfToken, const char *EndOfToken,
 228                        long int *Val) {
 229   if (Kind != tgpptoken_symbol)
 230     return false;
 231   char *e;
 232   *Val = strtol(BeginOfToken, &e, 10);
 233   return e == EndOfToken;
 234 }
 235
 236 TGPPTokenKind TGPPLexer::
 237 NextToken(const char **BeginOfToken, const char **EndOfToken) {
 238   bool IsBeginOfLine = WasEndOfLine;
 239   WasEndOfLine = false;
 240
 241   if (IsEndOfBuffer(CurPtr))
 242     return tgpptoken_end;
 243
 244   else if (IsInsideMacroStatement) {
 245     while (*CurPtr == ' ' || *CurPtr == '\t') // trim space, if any
 246       ++CurPtr;
 247
 248     const char *BeginOfSymbol = CurPtr;
 249
 250     if (IsNewLine()) {
 251       ++CurPtr;
 252       IsInsideMacroStatement = false;
 253       WasEndOfLine = true;
 254       return tgpptoken_newline;
 255     }
 256
 257     else if (*CurPtr == '[' || *CurPtr == ']' ||
 258              *CurPtr == '(' || *CurPtr == ')' ||
 259              *CurPtr == ',' || *CurPtr == '=') {
 260       *BeginOfToken = BeginOfSymbol;
 261       *EndOfToken = ++CurPtr;
 262       return tgpptoken_symbol;
 263     }
 264
 265     else if (*CurPtr == '_' || isalpha(*CurPtr)) {
 266       ++CurPtr;
 267       while (*CurPtr == '_' || isalnum(*CurPtr))
 268         ++CurPtr;
 269       *BeginOfToken = BeginOfSymbol;
 270       *EndOfToken = CurPtr;
 271       return tgpptoken_symbol;
 272     }
 273
 274     else if (*CurPtr == '+' || *CurPtr == '-' || isdigit(*CurPtr)) {
 275       ++CurPtr;
 276       while (isdigit(*CurPtr))
 277         ++CurPtr;
 278       *BeginOfToken = BeginOfSymbol;
 279       *EndOfToken = CurPtr;
 280       return tgpptoken_symbol;
 281     }
 282
 283     else {
 284       PrintError(BeginOfSymbol, "Unrecognizable token");
 285       return tgpptoken_error;
 286     }
 287   }
 288
 289   else if (*CurPtr == '#') {
 290     if (IsBeginOfLine &&
 291         (MatchPrefix("for", CurPtr + 1) ||
 292          MatchPrefix("end", CurPtr + 1))) {
 293       ++CurPtr;
 294       IsInsideMacroStatement = true;
 295       return NextToken(BeginOfToken, EndOfToken);
 296     }
 297
 298     // special token #"# is translate to literal "
 299     else if (CurPtr[1] == '"' && CurPtr[2] == '#') {
 300       *BeginOfToken = ++CurPtr;
 301       *EndOfToken = ++CurPtr;
 302       ++CurPtr;
 303       return tgpptoken_literal;
 304     }
 305
 306     else {
 307       const char *BeginOfVar = ++CurPtr; // trim '#'
 308       if (*CurPtr != '_' && !isalpha(*CurPtr)) {
 309         PrintError(BeginOfVar, "Variable must start with [_A-Za-z]: ");
 310         return tgpptoken_error;
 311       }
 312       while (*CurPtr == '_' || isalnum(*CurPtr))
 313         ++CurPtr;
 314       if (*CurPtr != '#') {
 315         PrintError(BeginOfVar, "Variable must end with #");
 316         return tgpptoken_error;
 317       }
 318       *BeginOfToken = BeginOfVar;
 319       *EndOfToken = CurPtr++; // trim '#'
 320       return tgpptoken_symbol;
 321     }
 322   }
 323
 324   const char *BeginOfLiteral = CurPtr;
 325   int CCommentLevel = 0;
 326   bool BCPLComment = false;
 327   bool StringLiteral = false;
 328   for (; !IsEndOfBuffer(CurPtr); ++CurPtr) {
 329     if (CCommentLevel > 0) {
 330       if (CurPtr[0] == '/' && CurPtr[1] == '*') {
 331         ++CurPtr;
 332         ++CCommentLevel;
 333       } else if (CurPtr[0] == '*' && CurPtr[1] == '/') {
 334         ++CurPtr;
 335         --CCommentLevel;
 336       } else if (IsNewLine())
 337         WasEndOfLine = true;
 338     }
 339
 340     else if (BCPLComment) {
 341       if (IsNewLine()) {
 342         WasEndOfLine = true;
 343         BCPLComment = false;
 344       }
 345     }
 346
 347     else if (StringLiteral) {
 348       // no string escape sequence in TableGen?
 349       if (*CurPtr == '"')
 350         StringLiteral = false;
 351     }
 352
 353     else if (CurPtr[0] == '/' && CurPtr[1] == '*') {
 354       ++CurPtr;
 355       ++CCommentLevel;
 356     }
 357
 358     else if (CurPtr[0] == '/' && CurPtr[1] == '/') {
 359       ++CurPtr;
 360       BCPLComment = true;
 361     }
 362
 363     else if (*CurPtr == '"')
 364       StringLiteral = true;
 365
 366     else if (IsNewLine()) {
 367       ++CurPtr;
 368       WasEndOfLine = true;
 369       break;
 370     }
 371
 372     else if (*CurPtr == '#')
 373       break;
 374   }
 375
 376   *BeginOfToken = BeginOfLiteral;
 377   *EndOfToken = CurPtr;
 378   return tgpptoken_literal;
 379 }
 380
 381 bool TGPPRecord::
 382 EvaluateFor(const TGPPEnvironment &Env, raw_fd_ostream &OS) const {
 383   std::vector<TGPPRange>::const_iterator ri, re;
 384
 385   // calculate the min size
 386   ri = IndexRanges.begin();
 387   re = IndexRanges.begin();
 388   size_t n = ri->size();
 389   for (; ri != re; ++ri) {
 390     size_t m = ri->size();
 391     if (m < n)
 392       n = m;
 393   }
 394
 395   for (size_t which_val = 0; which_val < n; ++which_val) {
 396     // construct nested environment
 397     TGPPEnvironment NestedEnv(Env);
 398     std::vector<std::string>::const_iterator vi = IndexVars.begin();
 399     for (ri = IndexRanges.begin(), re = IndexRanges.end();
 400         ri != re; ++vi, ++ri) {
 401       NestedEnv.insert(std::make_pair(*vi, ri->at(which_val)));
 402     }
 403     // evalute loop body
 404     for (TGPPRecords::const_iterator i = LoopBody.begin(), e = LoopBody.end();
 405         i != e; ++i)
 406       if (i->Evaluate(NestedEnv, OS))
 407         return true;
 408   }
 409
 410   return false;
 411 }
 412
 413 bool TGPPRecord::
 414 Evaluate(const TGPPEnvironment &Env, raw_fd_ostream &OS) const {
 415   switch (Kind) {
 416   case tgpprecord_for:
 417     return EvaluateFor(Env, OS);
 418   case tgpprecord_variable:
 419     return EvaluateVariable(Env, OS);
 420   case tgpprecord_literal:
 421     return EvaluateLiteral(Env, OS);
 422   default:
 423     PrintError("Unknown kind of record: " + Kind);
 424     return true;
 425   }
 426   return false;
 427 }
 428
 429 bool TGPreprocessor::ParseBlock(bool TopLevel) {
 430   TGPPTokenKind Kind;
 431   const char *BeginOfToken, *EndOfToken;
 432   while ((Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken)) !=
 433          tgpptoken_end) {
 434     std::string Symbol(BeginOfToken, EndOfToken);
 435     switch (Kind) {
 436     case tgpptoken_symbol:
 437       if (Symbol == "for") {
 438         if (ParseForLoop())
 439           return true;
 440       } else if (Symbol == "end") {
 441         if (TopLevel) {
 442           PrintError(BeginOfToken, "No block to end here");
 443           return true;
 444         }
 445         if ((Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken)) !=
 446             tgpptoken_newline) {
 447           PrintError(BeginOfToken, "Tokens after #end");
 448           return true;
 449         }
 450         return false;
 451       } else if (Symbol == "NAME") {
 452         // treat '#NAME#' as a literal
 453         CurRecords->push_back(
 454             TGPPRecord(tgpprecord_literal,
 455                        std::string("#NAME#")));
 456       } else {
 457         CurRecords->push_back(
 458             TGPPRecord(tgpprecord_variable,
 459                        std::string(BeginOfToken, EndOfToken)));
 460       }
 461       break;
 462     case tgpptoken_literal:
 463       CurRecords->push_back(
 464           TGPPRecord(tgpprecord_literal,
 465                      std::string(BeginOfToken, EndOfToken)));
 466       break;
 467     default:
 468       return true;
 469     }
 470   }
 471   return false;
 472 }
 473
 474 bool TGPreprocessor::ParseForLoop() {
 475   TGPPRecord ForLoopRecord(tgpprecord_for);
 476
 477   for (;;) {
 478     TGPPTokenKind Kind;
 479     const char *BeginOfToken, *EndOfToken;
 480
 481     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 482     if (!MatchIdentifier(Kind, BeginOfToken, EndOfToken)) {
 483       PrintError(BeginOfToken, "Not an identifier");
 484       return true;
 485     }
 486     std::string IndexVar(BeginOfToken, EndOfToken);
 487
 488     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 489     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, '=')) {
 490       PrintError(BeginOfToken, "Need a '=' here");
 491       return true;
 492     }
 493
 494     TGPPRange Range;
 495     if (ParseRange(&Range))
 496       return true;
 497     ForLoopRecord.AppendIndex(IndexVar, Range);
 498
 499     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 500     if (Kind == tgpptoken_newline)
 501       break;
 502     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ',')) {
 503       PrintError(BeginOfToken, "Need a ',' here");
 504       return true;
 505     }
 506   }
 507
 508   // open a new level
 509   TGPPRecords *LastCurRecords = CurRecords;
 510   CurRecords = ForLoopRecord.GetLoopBody();
 511
 512   if (ParseBlock(false))
 513     return true;
 514
 515   CurRecords = LastCurRecords;
 516   CurRecords->push_back(ForLoopRecord);
 517   return false;
 518 }
 519
 520 bool TGPreprocessor::ParseRange(TGPPRange *Range) {
 521   TGPPTokenKind Kind;
 522   const char *BeginOfToken, *EndOfToken;
 523
 524   Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 525
 526   if (MatchSymbol(Kind, BeginOfToken, EndOfToken, '[')) {
 527     for (;;) {
 528       Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 529       if (!MatchIdNum(Kind, BeginOfToken, EndOfToken)) {
 530         PrintError(BeginOfToken, "Need a identifier or a number here");
 531         return true;
 532       }
 533       Range->push_back(std::string(BeginOfToken, EndOfToken));
 534
 535       Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 536       if (MatchSymbol(Kind, BeginOfToken, EndOfToken, ']'))
 537         break;
 538       if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ',')) {
 539         PrintError(BeginOfToken, "Need a comma here");
 540         return true;
 541       }
 542     }
 543     return false;
 544   }
 545
 546   else if (MatchSymbol(Kind, BeginOfToken, EndOfToken, "sequence")) {
 547     long int from, to;
 548
 549     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 550     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, '(')) {
 551       PrintError(BeginOfToken, "Need a left parentheses here");
 552       return true;
 553     }
 554
 555     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 556     if (!MatchNumber(Kind, BeginOfToken, EndOfToken, &from)) {
 557       PrintError(BeginOfToken, "Not a number");
 558       return true;
 559     }
 560
 561     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 562     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ',')) {
 563       PrintError(BeginOfToken, "Need a comma here");
 564       return true;
 565     }
 566
 567     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 568     if (!MatchNumber(Kind, BeginOfToken, EndOfToken, &to)) {
 569       PrintError(BeginOfToken, "Not a number");
 570       return true;
 571     }
 572
 573     Kind = Lexer->NextToken(&BeginOfToken, &EndOfToken);
 574     if (!MatchSymbol(Kind, BeginOfToken, EndOfToken, ')')) {
 575       PrintError(BeginOfToken, "Need a right parentheses here");
 576       return true;
 577     }
 578
 579     *Range = TGPPRange(from, to);
 580     return false;
 581   }
 582
 583   PrintError(BeginOfToken, "illegal range of loop index");
 584   return true;
 585 }
 586
 587 bool TGPreprocessor::PreprocessFile() {
 588   TGPPLexer TheLexer(SrcMgr);
 589   TGPPRecords TopLevelRecords;
 590
 591   Lexer = &TheLexer;
 592   CurRecords = &TopLevelRecords;
 593   if (ParseBlock(true))
 594     return true;
 595
 596   TGPPEnvironment Env;
 597   for (TGPPRecords::const_iterator i = TopLevelRecords.begin(),
 598                                    e = TopLevelRecords.end();
 599       i != e; ++i)
 600     if (i->Evaluate(Env, Out.os()))
 601       return true;
 602
 603   return false;
 604 }