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