klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Parser.cpp
Go to the documentation of this file.
1 //===-- Parser.cpp --------------------------------------------------------===//
2 //
3 // The KLEE Symbolic Virtual Machine
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 "expr/Parser.h"
11 
12 #include "expr/Lexer.h"
13 
14 #include "klee/Config/Version.h"
15 #include "klee/Constraints.h"
16 #include "klee/ExprBuilder.h"
17 #include "klee/Solver.h"
18 #include "klee/util/ExprPPrinter.h"
19 
20 #include "llvm/ADT/APInt.h"
21 #include "llvm/Support/MemoryBuffer.h"
22 #include "llvm/Support/raw_ostream.h"
23 
24 #include <cassert>
25 #include <map>
26 #include <cstring>
27 
28 using namespace llvm;
29 using namespace klee;
30 using namespace klee::expr;
31 
32 namespace {
34  template<typename T>
35  struct ParseResult {
36  bool IsValid;
37  T Value;
38 
39  public:
40  ParseResult() : IsValid(false), Value() {}
41  ParseResult(T _Value) : IsValid(true), Value(_Value) {}
42  ParseResult(bool _IsValid, T _Value) : IsValid(_IsValid), Value(_Value) {}
43 
44  bool isValid() {
45  return IsValid;
46  }
47  T get() {
48  assert(IsValid && "get() on invalid ParseResult!");
49  return Value;
50  }
51  };
52 
53  class ExprResult {
54  bool IsValid;
55  ExprHandle Value;
56 
57  public:
58  ExprResult() : IsValid(false) {}
59  ExprResult(ExprHandle _Value) : IsValid(true), Value(_Value) {}
60  ExprResult(ref<ConstantExpr> _Value) : IsValid(true), Value(_Value.get()) {}
61  ExprResult(bool _IsValid, ExprHandle _Value) : IsValid(_IsValid), Value(_Value) {}
62 
63  bool isValid() {
64  return IsValid;
65  }
66  ExprHandle get() {
67  assert(IsValid && "get() on invalid ParseResult!");
68  return Value;
69  }
70  };
71 
72  typedef ParseResult<Decl*> DeclResult;
73  typedef ParseResult<Expr::Width> TypeResult;
74  typedef ParseResult<VersionHandle> VersionResult;
75  typedef ParseResult<uint64_t> IntegerResult;
76 
80  class NumberOrExprResult {
81  Token AsNumber;
82  ExprResult AsExpr;
83  bool IsNumber;
84 
85  public:
86  NumberOrExprResult() : IsNumber(false) {}
87  explicit NumberOrExprResult(Token _AsNumber) : AsNumber(_AsNumber),
88  IsNumber(true) {}
89  explicit NumberOrExprResult(ExprResult _AsExpr) : AsExpr(_AsExpr),
90  IsNumber(false) {}
91 
92  bool isNumber() const { return IsNumber; }
93  const Token &getNumber() const {
94  assert(IsNumber && "Invalid accessor call.");
95  return AsNumber;
96  }
97  const ExprResult &getExpr() const {
98  assert(!IsNumber && "Invalid accessor call.");
99  return AsExpr;
100  }
101  };
102 
104  class ParserImpl : public Parser {
105  typedef std::map<const std::string, const Identifier*> IdentifierTabTy;
106  typedef std::map<const Identifier*, ExprHandle> ExprSymTabTy;
107  typedef std::map<const Identifier*, VersionHandle> VersionSymTabTy;
108 
109  const std::string Filename;
110  const MemoryBuffer *TheMemoryBuffer;
111  ExprBuilder *Builder;
112 
113  Lexer TheLexer;
114  unsigned MaxErrors;
115  unsigned NumErrors;
116 
117  // FIXME: Use LLVM symbol tables?
118  IdentifierTabTy IdentifierTab;
119 
120  std::map<const Identifier*, const ArrayDecl*> ArraySymTab;
121  ExprSymTabTy ExprSymTab;
122  VersionSymTabTy VersionSymTab;
123 
125  Token Tok;
126 
128  unsigned ParenLevel;
130  unsigned SquareLevel;
131 
132  /* Core parsing functionality */
133 
134  const Identifier *GetOrCreateIdentifier(const Token &Tok);
135 
136  void GetNextNonCommentToken() {
137  do {
138  TheLexer.Lex(Tok);
139  } while (Tok.kind == Token::Comment);
140  }
141 
143  void ConsumeToken() {
144  assert(Tok.kind != Token::LParen && Tok.kind != Token::RParen &&
145  Tok.kind != Token::LSquare && Tok.kind != Token::RSquare);
146  GetNextNonCommentToken();
147  }
148 
151  void ConsumeExpectedToken(Token::Kind k) {
152  assert(Tok.kind != Token::LParen && Tok.kind != Token::RParen &&
153  Tok.kind != Token::LSquare && Tok.kind != Token::RSquare);
154  _ConsumeExpectedToken(k);
155  }
156  void _ConsumeExpectedToken(Token::Kind k) {
157  assert(Tok.kind == k && "Unexpected token!");
158  GetNextNonCommentToken();
159  }
160 
161  void ConsumeLParen() {
162  ++ParenLevel;
163  _ConsumeExpectedToken(Token::LParen);
164  }
165 
166  void ConsumeRParen() {
167  if (ParenLevel) // Cannot go below zero.
168  --ParenLevel;
169  _ConsumeExpectedToken(Token::RParen);
170  }
171 
172  void ConsumeLSquare() {
173  ++SquareLevel;
174  _ConsumeExpectedToken(Token::LSquare);
175  }
176 
177  void ConsumeRSquare() {
178  if (SquareLevel) // Cannot go below zero.
179  --SquareLevel;
180  _ConsumeExpectedToken(Token::RSquare);
181  }
182 
183  void ConsumeAnyToken() {
184  switch (Tok.kind) {
185  case Token::LParen: return ConsumeLParen();
186  case Token::RParen: return ConsumeRParen();
187  case Token::LSquare: return ConsumeLSquare();
188  case Token::RSquare: return ConsumeRSquare();
189  default:
190  return ConsumeToken();
191  }
192  }
193 
194  /* Utility functions */
195 
198  void SkipUntilRParen(unsigned Level) {
199  // FIXME: I keep wavering on whether it is an error to call this
200  // with the current token an rparen. In most cases this should
201  // have been handled differently (error reported,
202  // whatever). Audit & resolve.
203  assert(Level <= ParenLevel &&
204  "Refusing to skip until rparen at higher level.");
205  while (Tok.kind != Token::EndOfFile) {
206  if (Tok.kind == Token::RParen && ParenLevel == Level) {
207  ConsumeRParen();
208  break;
209  }
210  ConsumeAnyToken();
211  }
212  }
213 
216  void SkipUntilRParen() {
217  SkipUntilRParen(ParenLevel);
218  }
219 
223  void ExpectRParen(const char *Msg) {
224  if (Tok.kind == Token::EndOfFile) {
225  // FIXME: Combine with Msg
226  Error("expected ')' but found end-of-file.", Tok);
227  } else if (Tok.kind != Token::RParen) {
228  Error(Msg, Tok);
229  SkipUntilRParen();
230  } else {
231  ConsumeRParen();
232  }
233  }
234 
237  void SkipUntilRSquare(unsigned Level) {
238  // FIXME: I keep wavering on whether it is an error to call this
239  // with the current token an rparen. In most cases this should
240  // have been handled differently (error reported,
241  // whatever). Audit & resolve.
242  assert(Level <= ParenLevel &&
243  "Refusing to skip until rparen at higher level.");
244  while (Tok.kind != Token::EndOfFile) {
245  if (Tok.kind == Token::RSquare && ParenLevel == Level) {
246  ConsumeRSquare();
247  break;
248  }
249  ConsumeAnyToken();
250  }
251  }
252 
255  void SkipUntilRSquare() {
256  SkipUntilRSquare(ParenLevel);
257  }
258 
262  void ExpectRSquare(const char *Msg) {
263  if (Tok.kind == Token::EndOfFile) {
264  // FIXME: Combine with Msg
265  Error("expected ']' but found end-of-file.", Tok);
266  } else if (Tok.kind != Token::RSquare) {
267  Error(Msg, Tok);
268  SkipUntilRSquare();
269  } else {
270  ConsumeRSquare();
271  }
272  }
273 
274  /*** Grammar productions ****/
275 
276  /* Top level decls */
277 
278  DeclResult ParseArrayDecl();
279  DeclResult ParseExprVarDecl();
280  DeclResult ParseVersionVarDecl();
281  DeclResult ParseCommandDecl();
282 
283  /* Commands */
284 
285  DeclResult ParseQueryCommand();
286 
287  /* Etc. */
288 
289  NumberOrExprResult ParseNumberOrExpr();
290  IntegerResult ParseIntegerConstant(Expr::Width Type);
291 
292  ExprResult ParseExpr(TypeResult ExpectedType);
293  ExprResult ParseParenExpr(TypeResult ExpectedType);
294  ExprResult ParseUnaryParenExpr(const Token &Name,
295  unsigned Kind, bool IsFixed,
296  Expr::Width ResTy);
297  ExprResult ParseBinaryParenExpr(const Token &Name,
298  unsigned Kind, bool IsFixed,
299  Expr::Width ResTy);
300  ExprResult ParseSelectParenExpr(const Token &Name, Expr::Width ResTy);
301  ExprResult ParseConcatParenExpr(const Token &Name, Expr::Width ResTy);
302  ExprResult ParseExtractParenExpr(const Token &Name, Expr::Width ResTy);
303  ExprResult ParseAnyReadParenExpr(const Token &Name,
304  unsigned Kind,
305  Expr::Width ResTy);
306  void ParseMatchedBinaryArgs(const Token &Name,
307  TypeResult ExpectType,
308  ExprResult &LHS, ExprResult &RHS);
309  ExprResult ParseNumber(Expr::Width Width);
310  ExprResult ParseNumberToken(Expr::Width Width, const Token &Tok);
311 
312  VersionResult ParseVersionSpecifier();
313  VersionResult ParseVersion();
314 
315  TypeResult ParseTypeSpecifier();
316 
317  /*** Diagnostics ***/
318 
319  void Error(const char *Message, const Token &At);
320  void Error(const char *Message) { Error(Message, Tok); }
321 
322  public:
323  ParserImpl(const std::string _Filename,
324  const MemoryBuffer *MB,
325  ExprBuilder *_Builder) : Filename(_Filename),
326  TheMemoryBuffer(MB),
327  Builder(_Builder),
328  TheLexer(MB),
329  MaxErrors(~0u),
330  NumErrors(0) {}
331 
334  void Initialize() {
335  ParenLevel = SquareLevel = 0;
336 
337  ConsumeAnyToken();
338  }
339 
340  /* Parser interface implementation */
341 
342  virtual Decl *ParseTopLevelDecl();
343 
344  virtual void SetMaxErrors(unsigned N) {
345  MaxErrors = N;
346  }
347 
348  virtual unsigned GetNumErrors() const {
349  return NumErrors;
350  }
351  };
352 }
353 
354 const Identifier *ParserImpl::GetOrCreateIdentifier(const Token &Tok) {
355  // FIXME: Make not horribly inefficient please.
356  assert(Tok.kind == Token::Identifier && "Expected only identifier tokens.");
357  std::string Name(Tok.start, Tok.length);
358  IdentifierTabTy::iterator it = IdentifierTab.find(Name);
359  if (it != IdentifierTab.end())
360  return it->second;
361 
362  Identifier *I = new Identifier(Name);
363  IdentifierTab.insert(std::make_pair(Name, I));
364 
365  return I;
366 }
367 
368 Decl *ParserImpl::ParseTopLevelDecl() {
369  // Repeat until success or EOF.
370  while (Tok.kind != Token::EndOfFile) {
371  switch (Tok.kind) {
372  case Token::KWArray: {
373  DeclResult Res = ParseArrayDecl();
374  if (Res.isValid())
375  return Res.get();
376  break;
377  }
378 
379  case Token::LParen: {
380  DeclResult Res = ParseCommandDecl();
381  if (Res.isValid())
382  return Res.get();
383  break;
384  }
385 
386  default:
387  Error("expected 'array' or '(' token.");
388  ConsumeAnyToken();
389  }
390  }
391 
392  return 0;
393 }
394 
401 DeclResult ParserImpl::ParseArrayDecl() {
402  // FIXME: Recovery here is horrible, we need to scan to next decl start or
403  // something.
404  ConsumeExpectedToken(Token::KWArray);
405 
406  if (Tok.kind != Token::Identifier) {
407  Error("expected identifier token.");
408  return DeclResult();
409  }
410 
411  Token Name = Tok;
412  IntegerResult Size;
413  TypeResult DomainType;
414  TypeResult RangeType;
415  std::vector< ref<ConstantExpr> > Values;
416 
417  ConsumeToken();
418 
419  if (Tok.kind != Token::LSquare) {
420  Error("expected '['.");
421  goto exit;
422  }
423  ConsumeLSquare();
424 
425  if (Tok.kind != Token::RSquare) {
426  Size = ParseIntegerConstant(64);
427  }
428  if (Tok.kind != Token::RSquare) {
429  Error("expected ']'.");
430  goto exit;
431  }
432  ConsumeRSquare();
433 
434  if (Tok.kind != Token::Colon) {
435  Error("expected ':'.");
436  goto exit;
437  }
438  ConsumeExpectedToken(Token::Colon);
439 
440  DomainType = ParseTypeSpecifier();
441  if (Tok.kind != Token::Arrow) {
442  Error("expected '->'.");
443  goto exit;
444  }
445  ConsumeExpectedToken(Token::Arrow);
446 
447  RangeType = ParseTypeSpecifier();
448  if (Tok.kind != Token::Equals) {
449  Error("expected '='.");
450  goto exit;
451  }
452  ConsumeExpectedToken(Token::Equals);
453 
454  if (Tok.kind == Token::KWSymbolic) {
455  ConsumeExpectedToken(Token::KWSymbolic);
456  } else if (Tok.kind == Token::LSquare) {
457  ConsumeLSquare();
458  while (Tok.kind != Token::RSquare) {
459  if (Tok.kind == Token::EndOfFile) {
460  Error("unexpected end of file.");
461  goto exit;
462  }
463 
464  ExprResult Res = ParseNumber(RangeType.get());
465  if (Res.isValid())
466  Values.push_back(cast<ConstantExpr>(Res.get()));
467  }
468  ConsumeRSquare();
469  } else {
470  Error("expected 'symbolic' or '['.");
471  goto exit;
472  }
473 
474  // Type check size.
475  if (!Size.isValid()) {
476  if (Values.empty()) {
477  Error("unsized arrays are not yet supported.");
478  Size = 1;
479  } else {
480  Size = Values.size();
481  }
482  }
483 
484  if (!Values.empty()) {
485  if (Size.get() != Values.size()) {
486  // FIXME: Lame message.
487  Error("constant arrays must be completely specified.");
488  Values.clear();
489  }
490 
491  for (unsigned i = 0; i != Size.get(); ++i) {
492  // FIXME: Must be constant expression.
493  }
494  }
495 
496  // FIXME: Validate that size makes sense for domain type.
497 
498  if (DomainType.get() != Expr::Int32) {
499  Error("array domain must currently be w32.");
500  DomainType = Expr::Int32;
501  Values.clear();
502  }
503 
504  if (RangeType.get() != Expr::Int8) {
505  Error("array domain must currently be w8.");
506  RangeType = Expr::Int8;
507  Values.clear();
508  }
509 
510  // FIXME: Validate that this array is undeclared.
511 
512  exit:
513  if (!Size.isValid())
514  Size = 1;
515  if (!DomainType.isValid())
516  DomainType = 32;
517  if (!RangeType.isValid())
518  RangeType = 8;
519 
520  // FIXME: Array should take domain and range.
521  const Identifier *Label = GetOrCreateIdentifier(Name);
522  Array *Root;
523  if (!Values.empty())
524  Root = new Array(Label->Name, Size.get(),
525  &Values[0], &Values[0] + Values.size());
526  else
527  Root = new Array(Label->Name, Size.get());
528  ArrayDecl *AD = new ArrayDecl(Label, Size.get(),
529  DomainType.get(), RangeType.get(), Root);
530 
531  ArraySymTab.insert(std::make_pair(Label, AD));
532 
533  // Create the initial version reference.
534  VersionSymTab.insert(std::make_pair(Label,
535  UpdateList(Root, NULL)));
536 
537  return AD;
538 }
539 
544 DeclResult ParserImpl::ParseCommandDecl() {
545  ConsumeLParen();
546 
547  if (!Tok.isKeyword()) {
548  Error("malformed command.");
549  SkipUntilRParen();
550  return DeclResult();
551  }
552 
553  switch (Tok.kind) {
554  case Token::KWQuery:
555  return ParseQueryCommand();
556 
557  default:
558  Error("malformed command (unexpected keyword).");
559  SkipUntilRParen();
560  return DeclResult();
561  }
562 }
563 
568 DeclResult ParserImpl::ParseQueryCommand() {
569  std::vector<ExprHandle> Constraints;
570  std::vector<ExprHandle> Values;
571  std::vector<const Array*> Objects;
572  ExprResult Res;
573 
574  // FIXME: We need a command for this. Or something.
575  ExprSymTab.clear();
576  VersionSymTab.clear();
577 
578  // Reinsert initial array versions.
579  // FIXME: Remove this!
580  for (std::map<const Identifier*, const ArrayDecl*>::iterator
581  it = ArraySymTab.begin(), ie = ArraySymTab.end(); it != ie; ++it) {
582  VersionSymTab.insert(std::make_pair(it->second->Name,
583  UpdateList(it->second->Root, NULL)));
584  }
585 
586 
587  ConsumeExpectedToken(Token::KWQuery);
588  if (Tok.kind != Token::LSquare) {
589  Error("malformed query, expected constraint list.");
590  SkipUntilRParen();
591  return DeclResult();
592  }
593 
594  ConsumeLSquare();
595  // FIXME: Should avoid reading past unbalanced parens here.
596  while (Tok.kind != Token::RSquare) {
597  if (Tok.kind == Token::EndOfFile) {
598  Error("unexpected end of file.");
599  Res = ExprResult(Builder->Constant(0, Expr::Bool));
600  goto exit;
601  }
602 
603  ExprResult Constraint = ParseExpr(TypeResult(Expr::Bool));
604  if (Constraint.isValid())
605  Constraints.push_back(Constraint.get());
606  }
607  ConsumeRSquare();
608 
609  Res = ParseExpr(TypeResult(Expr::Bool));
610  if (!Res.isValid()) // Error emitted by ParseExpr.
611  Res = ExprResult(Builder->Constant(0, Expr::Bool));
612 
613  // Return if there are no optional lists of things to evaluate.
614  if (Tok.kind == Token::RParen)
615  goto exit;
616 
617  if (Tok.kind != Token::LSquare) {
618  Error("malformed query, expected expression list.");
619  SkipUntilRParen();
620  return DeclResult();
621  }
622 
623  ConsumeLSquare();
624  // FIXME: Should avoid reading past unbalanced parens here.
625  while (Tok.kind != Token::RSquare) {
626  if (Tok.kind == Token::EndOfFile) {
627  Error("unexpected end of file.");
628  goto exit;
629  }
630 
631  ExprResult Res = ParseExpr(TypeResult());
632  if (Res.isValid())
633  Values.push_back(Res.get());
634  }
635  ConsumeRSquare();
636 
637  // Return if there are no optional lists of things to evaluate.
638  if (Tok.kind == Token::RParen)
639  goto exit;
640 
641  if (Tok.kind != Token::LSquare) {
642  Error("malformed query, expected array list.");
643  SkipUntilRParen();
644  return DeclResult();
645  }
646 
647  ConsumeLSquare();
648  // FIXME: Should avoid reading past unbalanced parens here.
649  while (Tok.kind != Token::RSquare) {
650  if (Tok.kind == Token::EndOfFile) {
651  Error("unexpected end of file.");
652  goto exit;
653  }
654 
655  // FIXME: Factor out.
656  if (Tok.kind != Token::Identifier) {
657  Error("unexpected token.");
658  ConsumeToken();
659  continue;
660  }
661 
662  Token LTok = Tok;
663  const Identifier *Label = GetOrCreateIdentifier(Tok);
664  ConsumeToken();
665 
666  // Lookup array.
667  std::map<const Identifier*, const ArrayDecl*>::iterator
668  it = ArraySymTab.find(Label);
669 
670  if (it == ArraySymTab.end()) {
671  Error("unknown array", LTok);
672  } else {
673  Objects.push_back(it->second->Root);
674  }
675  }
676  ConsumeRSquare();
677 
678  exit:
679  if (Tok.kind != Token::EndOfFile)
680  ExpectRParen("unexpected argument to 'query'.");
681  return new QueryCommand(Constraints, Res.get(), Values, Objects);
682 }
683 
686 NumberOrExprResult ParserImpl::ParseNumberOrExpr() {
687  if (Tok.kind == Token::Number){
688  Token Num = Tok;
689  ConsumeToken();
690  return NumberOrExprResult(Num);
691  } else {
692  return NumberOrExprResult(ParseExpr(TypeResult()));
693  }
694 }
695 
704 ExprResult ParserImpl::ParseExpr(TypeResult ExpectedType) {
705  // FIXME: Is it right to need to do this here?
706  if (Tok.kind == Token::EndOfFile) {
707  Error("unexpected end of file.");
708  return ExprResult();
709  }
710 
711  if (Tok.kind == Token::KWFalse || Tok.kind == Token::KWTrue) {
712  bool Value = Tok.kind == Token::KWTrue;
713  ConsumeToken();
714  return ExprResult(Builder->Constant(Value, Expr::Bool));
715  }
716 
717  if (Tok.kind == Token::Number) {
718  if (!ExpectedType.isValid()) {
719  Error("cannot infer type of number.");
720  ConsumeToken();
721  return ExprResult();
722  }
723 
724  return ParseNumber(ExpectedType.get());
725  }
726 
727  const Identifier *Label = 0;
728  if (Tok.kind == Token::Identifier) {
729  Token LTok = Tok;
730  Label = GetOrCreateIdentifier(Tok);
731  ConsumeToken();
732 
733  if (Tok.kind != Token::Colon) {
734  ExprSymTabTy::iterator it = ExprSymTab.find(Label);
735 
736  if (it == ExprSymTab.end()) {
737  Error("invalid expression label reference.", LTok);
738  return ExprResult();
739  }
740 
741  return it->second;
742  }
743 
744  ConsumeToken();
745  if (ExprSymTab.count(Label)) {
746  Error("duplicate expression label definition.", LTok);
747  Label = 0;
748  }
749  }
750 
751  Token Start = Tok;
752  ExprResult Res = ParseParenExpr(ExpectedType);
753  if (!Res.isValid()) {
754  // If we know the type, define the identifier just so we don't get
755  // use-of-undef errors.
756  // FIXME: Maybe we should let the symbol table map to invalid
757  // entries?
758  if (Label && ExpectedType.isValid()) {
759  ref<Expr> Value = Builder->Constant(0, ExpectedType.get());
760  ExprSymTab.insert(std::make_pair(Label, Value));
761  }
762  return Res;
763  } else if (ExpectedType.isValid()) {
764  // Type check result.
765  if (Res.get()->getWidth() != ExpectedType.get()) {
766  // FIXME: Need more info, and range
767  Error("expression has incorrect type.", Start);
768  return ExprResult();
769  }
770  }
771 
772  if (Label)
773  ExprSymTab.insert(std::make_pair(Label, Res.get()));
774  return Res;
775 }
776 
777 // Additional kinds for macro forms.
778 enum MacroKind {
779  eMacroKind_ReadLSB = Expr::LastKind + 1, // Multibyte read
780  eMacroKind_ReadMSB, // Multibyte write
781  eMacroKind_Neg, // 0 - x // CrC: will disappear soon
782  eMacroKind_Concat, // Magic concatenation syntax
784 };
785 
796 static bool LookupExprInfo(const Token &Tok, unsigned &Kind,
797  bool &IsFixed, int &NumArgs) {
798 #define SetOK(kind, isfixed, numargs) (Kind=kind, IsFixed=isfixed,\
799  NumArgs=numargs, true)
800  assert(Tok.kind == Token::Identifier && "Unexpected token.");
801 
802  switch (Tok.length) {
803  case 2:
804  if (memcmp(Tok.start, "Eq", 2) == 0)
805  return SetOK(Expr::Eq, false, 2);
806  if (memcmp(Tok.start, "Ne", 2) == 0)
807  return SetOK(Expr::Ne, false, 2);
808 
809  if (memcmp(Tok.start, "Or", 2) == 0)
810  return SetOK(Expr::Or, true, 2);
811  break;
812 
813  case 3:
814  if (memcmp(Tok.start, "Add", 3) == 0)
815  return SetOK(Expr::Add, true, 2);
816  if (memcmp(Tok.start, "Sub", 3) == 0)
817  return SetOK(Expr::Sub, true, 2);
818  if (memcmp(Tok.start, "Mul", 3) == 0)
819  return SetOK(Expr::Mul, true, 2);
820 
821  if (memcmp(Tok.start, "Not", 3) == 0)
822  return SetOK(Expr::Not, true, 1);
823  if (memcmp(Tok.start, "And", 3) == 0)
824  return SetOK(Expr::And, true, 2);
825  if (memcmp(Tok.start, "Shl", 3) == 0)
826  return SetOK(Expr::Shl, true, 2);
827  if (memcmp(Tok.start, "Xor", 3) == 0)
828  return SetOK(Expr::Xor, true, 2);
829 
830  if (memcmp(Tok.start, "Ult", 3) == 0)
831  return SetOK(Expr::Ult, false, 2);
832  if (memcmp(Tok.start, "Ule", 3) == 0)
833  return SetOK(Expr::Ule, false, 2);
834  if (memcmp(Tok.start, "Ugt", 3) == 0)
835  return SetOK(Expr::Ugt, false, 2);
836  if (memcmp(Tok.start, "Uge", 3) == 0)
837  return SetOK(Expr::Uge, false, 2);
838  if (memcmp(Tok.start, "Slt", 3) == 0)
839  return SetOK(Expr::Slt, false, 2);
840  if (memcmp(Tok.start, "Sle", 3) == 0)
841  return SetOK(Expr::Sle, false, 2);
842  if (memcmp(Tok.start, "Sgt", 3) == 0)
843  return SetOK(Expr::Sgt, false, 2);
844  if (memcmp(Tok.start, "Sge", 3) == 0)
845  return SetOK(Expr::Sge, false, 2);
846  break;
847 
848 
849 
850  case 4:
851  if (memcmp(Tok.start, "Read", 4) == 0)
852  return SetOK(Expr::Read, true, -1);
853  if (memcmp(Tok.start, "AShr", 4) == 0)
854  return SetOK(Expr::AShr, true, 2);
855  if (memcmp(Tok.start, "LShr", 4) == 0)
856  return SetOK(Expr::LShr, true, 2);
857 
858  if (memcmp(Tok.start, "UDiv", 4) == 0)
859  return SetOK(Expr::UDiv, true, 2);
860  if (memcmp(Tok.start, "SDiv", 4) == 0)
861  return SetOK(Expr::SDiv, true, 2);
862  if (memcmp(Tok.start, "URem", 4) == 0)
863  return SetOK(Expr::URem, true, 2);
864  if (memcmp(Tok.start, "SRem", 4) == 0)
865  return SetOK(Expr::SRem, true, 2);
866 
867  if (memcmp(Tok.start, "SExt", 4) == 0)
868  return SetOK(Expr::SExt, false, 1);
869  if (memcmp(Tok.start, "ZExt", 4) == 0)
870  return SetOK(Expr::ZExt, false, 1);
871  break;
872 
873  case 6:
874  if (memcmp(Tok.start, "Concat", 6) == 0)
875  return SetOK(eMacroKind_Concat, false, -1);
876  if (memcmp(Tok.start, "Select", 6) == 0)
877  return SetOK(Expr::Select, false, 3);
878  break;
879 
880  case 7:
881  if (memcmp(Tok.start, "Extract", 7) == 0)
882  return SetOK(Expr::Extract, false, -1);
883  if (memcmp(Tok.start, "ReadLSB", 7) == 0)
884  return SetOK(eMacroKind_ReadLSB, true, -1);
885  if (memcmp(Tok.start, "ReadMSB", 7) == 0)
886  return SetOK(eMacroKind_ReadMSB, true, -1);
887  break;
888  }
889 
890  return false;
891 #undef SetOK
892 }
893 
901 ExprResult ParserImpl::ParseParenExpr(TypeResult FIXME_UNUSED) {
902  if (Tok.kind != Token::LParen) {
903  Error("unexpected token.");
904  ConsumeAnyToken();
905  return ExprResult();
906  }
907 
908  ConsumeLParen();
909 
910  // Check for coercion case (w32 11).
911  if (Tok.kind == Token::KWWidth) {
912  TypeResult ExpectedType = ParseTypeSpecifier();
913 
914  if (Tok.kind != Token::Number) {
915  Error("coercion can only apply to a number.");
916  SkipUntilRParen();
917  return ExprResult();
918  }
919 
920  // Make sure this was a type specifier we support.
921  ExprResult Res;
922  if (ExpectedType.isValid())
923  Res = ParseNumber(ExpectedType.get());
924  else
925  ConsumeToken();
926 
927  ExpectRParen("unexpected argument in coercion.");
928  return Res;
929  }
930 
931  if (Tok.kind != Token::Identifier) {
932  Error("unexpected token, expected expression.");
933  SkipUntilRParen();
934  return ExprResult();
935  }
936 
937  Token Name = Tok;
938  ConsumeToken();
939 
940  // FIXME: Use invalid type (i.e. width==0)?
941  Token TypeTok = Tok;
942  bool HasType = TypeTok.kind == Token::KWWidth;
943  TypeResult Type = HasType ? ParseTypeSpecifier() : Expr::Bool;
944 
945  // FIXME: For now just skip to rparen on error. It might be nice
946  // to try and actually parse the child nodes though for error
947  // messages & better recovery?
948  if (!Type.isValid()) {
949  SkipUntilRParen();
950  return ExprResult();
951  }
952  Expr::Width ResTy = Type.get();
953 
954  unsigned ExprKind;
955  bool IsFixed;
956  int NumArgs;
957  if (!LookupExprInfo(Name, ExprKind, IsFixed, NumArgs)) {
958  // FIXME: For now just skip to rparen on error. It might be nice
959  // to try and actually parse the child nodes though for error
960  // messages & better recovery?
961  Error("unknown expression kind.", Name);
962  SkipUntilRParen();
963  return ExprResult();
964  }
965 
966  // See if we have to parse this form specially.
967  if (NumArgs == -1) {
968  switch (ExprKind) {
969  case eMacroKind_Concat:
970  return ParseConcatParenExpr(Name, ResTy);
971 
972  case Expr::Extract:
973  return ParseExtractParenExpr(Name, ResTy);
974 
975  case eMacroKind_ReadLSB:
976  case eMacroKind_ReadMSB:
977  case Expr::Read:
978  return ParseAnyReadParenExpr(Name, ExprKind, ResTy);
979 
980  default:
981  Error("internal error, unimplemented special form.", Name);
982  SkipUntilRParen();
983  return ExprResult(Builder->Constant(0, ResTy));
984  }
985  }
986 
987  switch (NumArgs) {
988  case 1:
989  return ParseUnaryParenExpr(Name, ExprKind, IsFixed, ResTy);
990  case 2:
991  return ParseBinaryParenExpr(Name, ExprKind, IsFixed, ResTy);
992  case 3:
993  if (ExprKind == Expr::Select)
994  return ParseSelectParenExpr(Name, ResTy);
995  default:
996  assert(0 && "Invalid argument kind (number of args).");
997  return ExprResult();
998  }
999 }
1000 
1001 ExprResult ParserImpl::ParseUnaryParenExpr(const Token &Name,
1002  unsigned Kind, bool IsFixed,
1003  Expr::Width ResTy) {
1004  if (Tok.kind == Token::RParen) {
1005  Error("unexpected end of arguments.", Name);
1006  ConsumeRParen();
1007  return Builder->Constant(0, ResTy);
1008  }
1009 
1010  ExprResult Arg = ParseExpr(IsFixed ? ResTy : TypeResult());
1011  if (!Arg.isValid())
1012  Arg = Builder->Constant(0, ResTy);
1013 
1014  ExpectRParen("unexpected argument in unary expression.");
1015  ExprHandle E = Arg.get();
1016  switch (Kind) {
1017  case eMacroKind_Neg:
1018  return Builder->Sub(Builder->Constant(0, E->getWidth()), E);
1019  case Expr::Not:
1020  // FIXME: Type check arguments.
1021  return Builder->Not(E);
1022  case Expr::SExt:
1023  // FIXME: Type check arguments.
1024  return Builder->SExt(E, ResTy);
1025  case Expr::ZExt:
1026  // FIXME: Type check arguments.
1027  return Builder->ZExt(E, ResTy);
1028  default:
1029  Error("internal error, unhandled kind.", Name);
1030  return Builder->Constant(0, ResTy);
1031  }
1032 }
1033 
1040 void ParserImpl::ParseMatchedBinaryArgs(const Token &Name,
1041  TypeResult ExpectType,
1042  ExprResult &LHS, ExprResult &RHS) {
1043  if (Tok.kind == Token::RParen) {
1044  Error("unexpected end of arguments.", Name);
1045  ConsumeRParen();
1046  return;
1047  }
1048 
1049  // Avoid NumberOrExprResult overhead and give more precise
1050  // diagnostics when we know the type.
1051  if (ExpectType.isValid()) {
1052  LHS = ParseExpr(ExpectType);
1053  if (Tok.kind == Token::RParen) {
1054  Error("unexpected end of arguments.", Name);
1055  ConsumeRParen();
1056  return;
1057  }
1058  RHS = ParseExpr(ExpectType);
1059  } else {
1060  NumberOrExprResult LHS_NOE = ParseNumberOrExpr();
1061 
1062  if (Tok.kind == Token::RParen) {
1063  Error("unexpected end of arguments.", Name);
1064  ConsumeRParen();
1065  return;
1066  }
1067 
1068  if (LHS_NOE.isNumber()) {
1069  NumberOrExprResult RHS_NOE = ParseNumberOrExpr();
1070 
1071  if (RHS_NOE.isNumber()) {
1072  Error("ambiguous arguments to expression.", Name);
1073  } else {
1074  RHS = RHS_NOE.getExpr();
1075  if (RHS.isValid())
1076  LHS = ParseNumberToken(RHS.get()->getWidth(), LHS_NOE.getNumber());
1077  }
1078  } else {
1079  LHS = LHS_NOE.getExpr();
1080  if (!LHS.isValid()) {
1081  // FIXME: Should suppress ambiguity warnings here.
1082  RHS = ParseExpr(TypeResult());
1083  } else {
1084  RHS = ParseExpr(LHS.get()->getWidth());
1085  }
1086  }
1087  }
1088 
1089  ExpectRParen("unexpected argument to expression.");
1090 }
1091 
1092 ExprResult ParserImpl::ParseBinaryParenExpr(const Token &Name,
1093  unsigned Kind, bool IsFixed,
1094  Expr::Width ResTy) {
1095  ExprResult LHS, RHS;
1096  ParseMatchedBinaryArgs(Name, IsFixed ? TypeResult(ResTy) : TypeResult(),
1097  LHS, RHS);
1098  if (!LHS.isValid() || !RHS.isValid())
1099  return Builder->Constant(0, ResTy);
1100 
1101  ref<Expr> LHS_E = LHS.get(), RHS_E = RHS.get();
1102  if (LHS_E->getWidth() != RHS_E->getWidth()) {
1103  Error("type widths do not match in binary expression", Name);
1104  return Builder->Constant(0, ResTy);
1105  }
1106 
1107  switch (Kind) {
1108  case Expr::Add: return Builder->Add(LHS_E, RHS_E);
1109  case Expr::Sub: return Builder->Sub(LHS_E, RHS_E);
1110  case Expr::Mul: return Builder->Mul(LHS_E, RHS_E);
1111  case Expr::UDiv: return Builder->UDiv(LHS_E, RHS_E);
1112  case Expr::SDiv: return Builder->SDiv(LHS_E, RHS_E);
1113  case Expr::URem: return Builder->URem(LHS_E, RHS_E);
1114  case Expr::SRem: return Builder->SRem(LHS_E, RHS_E);
1115 
1116  case Expr::AShr: return Builder->AShr(LHS_E, RHS_E);
1117  case Expr::LShr: return Builder->LShr(LHS_E, RHS_E);
1118  case Expr::Shl: return Builder->Shl(LHS_E, RHS_E);
1119 
1120  case Expr::And: return Builder->And(LHS_E, RHS_E);
1121  case Expr::Or: return Builder->Or(LHS_E, RHS_E);
1122  case Expr::Xor: return Builder->Xor(LHS_E, RHS_E);
1123 
1124  case Expr::Eq: return Builder->Eq(LHS_E, RHS_E);
1125  case Expr::Ne: return Builder->Ne(LHS_E, RHS_E);
1126  case Expr::Ult: return Builder->Ult(LHS_E, RHS_E);
1127  case Expr::Ule: return Builder->Ule(LHS_E, RHS_E);
1128  case Expr::Ugt: return Builder->Ugt(LHS_E, RHS_E);
1129  case Expr::Uge: return Builder->Uge(LHS_E, RHS_E);
1130  case Expr::Slt: return Builder->Slt(LHS_E, RHS_E);
1131  case Expr::Sle: return Builder->Sle(LHS_E, RHS_E);
1132  case Expr::Sgt: return Builder->Sgt(LHS_E, RHS_E);
1133  case Expr::Sge: return Builder->Sge(LHS_E, RHS_E);
1134  default:
1135  Error("FIXME: unhandled kind.", Name);
1136  return Builder->Constant(0, ResTy);
1137  }
1138 }
1139 
1140 ExprResult ParserImpl::ParseSelectParenExpr(const Token &Name,
1141  Expr::Width ResTy) {
1142  // FIXME: Why does this need to be here?
1143  if (Tok.kind == Token::RParen) {
1144  Error("unexpected end of arguments.", Name);
1145  ConsumeRParen();
1146  return Builder->Constant(0, ResTy);
1147  }
1148 
1149  ExprResult Cond = ParseExpr(Expr::Bool);
1150  ExprResult LHS, RHS;
1151  ParseMatchedBinaryArgs(Name, ResTy, LHS, RHS);
1152  if (!Cond.isValid() || !LHS.isValid() || !RHS.isValid())
1153  return Builder->Constant(0, ResTy);
1154  return Builder->Select(Cond.get(), LHS.get(), RHS.get());
1155 }
1156 
1157 
1158 // FIXME: Rewrite to only accept binary form. Make type optional.
1159 ExprResult ParserImpl::ParseConcatParenExpr(const Token &Name,
1160  Expr::Width ResTy) {
1161  std::vector<ExprHandle> Kids;
1162 
1163  unsigned Width = 0;
1164  while (Tok.kind != Token::RParen) {
1165  ExprResult E = ParseExpr(TypeResult());
1166 
1167  // Skip to end of expr on error.
1168  if (!E.isValid()) {
1169  SkipUntilRParen();
1170  return Builder->Constant(0, ResTy);
1171  }
1172 
1173  Kids.push_back(E.get());
1174  Width += E.get()->getWidth();
1175  }
1176 
1177  ConsumeRParen();
1178 
1179  if (Width != ResTy) {
1180  Error("concat does not match expected result size.");
1181  return Builder->Constant(0, ResTy);
1182  }
1183 
1184  // FIXME: Use builder!
1185  return ConcatExpr::createN(Kids.size(), &Kids[0]);
1186 }
1187 
1188 IntegerResult ParserImpl::ParseIntegerConstant(Expr::Width Type) {
1189  ExprResult Res = ParseNumber(Type);
1190 
1191  if (!Res.isValid())
1192  return IntegerResult();
1193 
1194  return cast<ConstantExpr>(Res.get())->getZExtValue(Type);
1195 }
1196 
1197 ExprResult ParserImpl::ParseExtractParenExpr(const Token &Name,
1198  Expr::Width ResTy) {
1199  IntegerResult OffsetExpr = ParseIntegerConstant(Expr::Int32);
1200  ExprResult Child = ParseExpr(TypeResult());
1201 
1202  ExpectRParen("unexpected argument to expression.");
1203 
1204  if (!OffsetExpr.isValid() || !Child.isValid())
1205  return Builder->Constant(0, ResTy);
1206 
1207  unsigned Offset = (unsigned) OffsetExpr.get();
1208  if (Offset + ResTy > Child.get()->getWidth()) {
1209  Error("extract out-of-range of child expression.", Name);
1210  return Builder->Constant(0, ResTy);
1211  }
1212 
1213  return Builder->Extract(Child.get(), Offset, ResTy);
1214 }
1215 
1216 ExprResult ParserImpl::ParseAnyReadParenExpr(const Token &Name,
1217  unsigned Kind,
1218  Expr::Width ResTy) {
1219  NumberOrExprResult Index = ParseNumberOrExpr();
1220  VersionResult Array = ParseVersionSpecifier();
1221  ExpectRParen("unexpected argument in read expression.");
1222 
1223  if (!Array.isValid())
1224  return Builder->Constant(0, ResTy);
1225 
1226  // FIXME: Need generic way to get array width. Needs to work with
1227  // anonymous arrays.
1228  Expr::Width ArrayDomainType = Expr::Int32;
1229  Expr::Width ArrayRangeType = Expr::Int8;
1230 
1231  // Coerce number to correct type.
1232  ExprResult IndexExpr;
1233  if (Index.isNumber())
1234  IndexExpr = ParseNumberToken(ArrayDomainType, Index.getNumber());
1235  else
1236  IndexExpr = Index.getExpr();
1237 
1238  if (!IndexExpr.isValid())
1239  return Builder->Constant(0, ResTy);
1240  else if (IndexExpr.get()->getWidth() != ArrayDomainType) {
1241  Error("index width does not match array domain.");
1242  return Builder->Constant(0, ResTy);
1243  }
1244 
1245  // FIXME: Check range width.
1246 
1247  switch (Kind) {
1248  default:
1249  assert(0 && "Invalid kind.");
1250  return Builder->Constant(0, ResTy);
1251  case eMacroKind_ReadLSB:
1252  case eMacroKind_ReadMSB: {
1253  unsigned NumReads = ResTy / ArrayRangeType;
1254  if (ResTy != NumReads*ArrayRangeType) {
1255  Error("invalid ordered read (not multiple of range type).", Name);
1256  return Builder->Constant(0, ResTy);
1257  }
1258  std::vector<ExprHandle> Kids(NumReads);
1259  ExprHandle Index = IndexExpr.get();
1260  for (unsigned i=0; i != NumReads; ++i) {
1261  // FIXME: We rely on folding here to not complicate things to where the
1262  // Read macro pattern fails to match.
1263  ExprHandle OffsetIndex = Index;
1264  if (i)
1265  OffsetIndex = AddExpr::create(OffsetIndex,
1266  Builder->Constant(i, ArrayDomainType));
1267  Kids[i] = Builder->Read(Array.get(), OffsetIndex);
1268  }
1269  if (Kind == eMacroKind_ReadLSB)
1270  std::reverse(Kids.begin(), Kids.end());
1271  // FIXME: Use builder!
1272  return ConcatExpr::createN(NumReads, &Kids[0]);
1273  }
1274  case Expr::Read:
1275  return Builder->Read(Array.get(), IndexExpr.get());
1276  }
1277 }
1278 
1281 VersionResult ParserImpl::ParseVersionSpecifier() {
1282  const Identifier *Label = 0;
1283  if (Tok.kind == Token::Identifier) {
1284  Token LTok = Tok;
1285  Label = GetOrCreateIdentifier(Tok);
1286  ConsumeToken();
1287 
1288  if (Tok.kind != Token::Colon) {
1289  VersionSymTabTy::iterator it = VersionSymTab.find(Label);
1290 
1291  if (it == VersionSymTab.end()) {
1292  Error("invalid version reference.", LTok);
1293  return VersionResult(false, UpdateList(0, NULL));
1294  }
1295 
1296  return it->second;
1297  }
1298 
1299  ConsumeToken();
1300  if (VersionSymTab.count(Label)) {
1301  Error("duplicate update list label definition.", LTok);
1302  Label = 0;
1303  }
1304  }
1305 
1306  VersionResult Res = ParseVersion();
1307  // Define update list to avoid use-of-undef errors.
1308  if (!Res.isValid()) {
1309  Res = VersionResult(true, UpdateList(new Array("", 0), NULL));
1310  }
1311 
1312  if (Label)
1313  VersionSymTab.insert(std::make_pair(Label, Res.get()));
1314  return Res;
1315 }
1316 
1317 namespace {
1320  struct WriteInfo {
1321  NumberOrExprResult LHS;
1322  NumberOrExprResult RHS;
1323  Token LHSTok;
1324  Token RHSTok;
1325 
1326  WriteInfo(NumberOrExprResult _LHS, NumberOrExprResult _RHS,
1327  Token _LHSTok, Token _RHSTok) : LHS(_LHS), RHS(_RHS),
1328  LHSTok(_LHSTok), RHSTok(_RHSTok) {
1329  }
1330  };
1331 }
1332 
1336 VersionResult ParserImpl::ParseVersion() {
1337  if (Tok.kind != Token::LSquare)
1338  return VersionResult(false, UpdateList(0, NULL));
1339 
1340  std::vector<WriteInfo> Writes;
1341  ConsumeLSquare();
1342  for (;;) {
1343  Token LHSTok = Tok;
1344  NumberOrExprResult LHS = ParseNumberOrExpr();
1345 
1346  if (Tok.kind != Token::Equals) {
1347  Error("expected '='.", Tok);
1348  break;
1349  }
1350 
1351  ConsumeToken();
1352  Token RHSTok = Tok;
1353  NumberOrExprResult RHS = ParseNumberOrExpr();
1354 
1355  Writes.push_back(WriteInfo(LHS, RHS, LHSTok, RHSTok));
1356 
1357  if (Tok.kind == Token::Comma)
1358  ConsumeToken();
1359  else
1360  break;
1361  }
1362  ExpectRSquare("expected close of update list");
1363 
1364  VersionHandle Base(0, NULL);
1365 
1366  if (Tok.kind != Token::At) {
1367  Error("expected '@'.", Tok);
1368  return VersionResult(false, UpdateList(0, NULL));
1369  }
1370 
1371  ConsumeExpectedToken(Token::At);
1372 
1373  VersionResult BaseRes = ParseVersionSpecifier();
1374  if (!BaseRes.isValid())
1375  return BaseRes;
1376 
1377  Base = BaseRes.get();
1378 
1379  Expr::Width ArrayDomainType = Expr::Int32;
1380  Expr::Width ArrayRangeType = Expr::Int8;
1381 
1382  for (std::vector<WriteInfo>::reverse_iterator it = Writes.rbegin(),
1383  ie = Writes.rend(); it != ie; ++it) {
1384  const WriteInfo &WI = *it;
1385  ExprResult LHS, RHS;
1386  // FIXME: This can be factored into common helper for coercing a
1387  // NumberOrExpr into an Expr.
1388  if (WI.LHS.isNumber()) {
1389  LHS = ParseNumberToken(ArrayDomainType, WI.LHS.getNumber());
1390  } else {
1391  LHS = WI.LHS.getExpr();
1392  if (LHS.isValid() && LHS.get()->getWidth() != ArrayDomainType) {
1393  Error("invalid write index (doesn't match array domain).", WI.LHSTok);
1394  LHS = ExprResult();
1395  }
1396  }
1397 
1398  if (WI.RHS.isNumber()) {
1399  RHS = ParseNumberToken(ArrayRangeType, WI.RHS.getNumber());
1400  } else {
1401  RHS = WI.RHS.getExpr();
1402  if (RHS.isValid() && RHS.get()->getWidth() != ArrayRangeType) {
1403  Error("invalid write value (doesn't match array range).", WI.RHSTok);
1404  RHS = ExprResult();
1405  }
1406  }
1407 
1408  if (LHS.isValid() && RHS.isValid())
1409  Base.extend(LHS.get(), RHS.get());
1410  }
1411 
1412  return Base;
1413 }
1414 
1416 ExprResult ParserImpl::ParseNumber(Expr::Width Type) {
1417  ExprResult Res = ParseNumberToken(Type, Tok);
1418  ConsumeExpectedToken(Token::Number);
1419  return Res;
1420 }
1421 
1424 ExprResult ParserImpl::ParseNumberToken(Expr::Width Type, const Token &Tok) {
1425  const char *S = Tok.start;
1426  unsigned N = Tok.length;
1427  unsigned Radix = 10, RadixBits = 4;
1428  bool HasMinus = false;
1429 
1430  // Detect +/- (a number token cannot have both).
1431  if (S[0] == '+') {
1432  ++S;
1433  --N;
1434  } else if (S[0] == '-') {
1435  HasMinus = true;
1436  ++S;
1437  --N;
1438  }
1439 
1440  // Detect 0[box].
1441  if ((Tok.length >= 2 && S[0] == '0') &&
1442  (S[1] == 'b' || S[1] == 'o' || S[1] == 'x')) {
1443  if (S[1] == 'b') {
1444  Radix = 2;
1445  RadixBits = 1;
1446  } else if (S[1] == 'o') {
1447  Radix = 8;
1448  RadixBits = 3;
1449  } else {
1450  Radix = 16;
1451  RadixBits = 4;
1452  }
1453  S += 2;
1454  N -= 2;
1455 
1456  // Diagnose 0[box] with no trailing digits.
1457  if (!N) {
1458  Error("invalid numeric token (no digits).", Tok);
1459  return Builder->Constant(0, Type);
1460  }
1461  }
1462 
1463  // This is a simple but slow way to handle overflow.
1464  APInt Val(RadixBits * N, 0);
1465  APInt RadixVal(Val.getBitWidth(), Radix);
1466  APInt DigitVal(Val.getBitWidth(), 0);
1467  for (unsigned i=0; i<N; ++i) {
1468  unsigned Digit, Char = S[i];
1469 
1470  if (Char == '_')
1471  continue;
1472 
1473  if ('0' <= Char && Char <= '9')
1474  Digit = Char - '0';
1475  else if ('a' <= Char && Char <= 'z')
1476  Digit = Char - 'a' + 10;
1477  else if ('A' <= Char && Char <= 'Z')
1478  Digit = Char - 'A' + 10;
1479  else {
1480  Error("invalid character in numeric token.", Tok);
1481  return Builder->Constant(0, Type);
1482  }
1483 
1484  if (Digit >= Radix) {
1485  Error("invalid character in numeric token (out of range).", Tok);
1486  return Builder->Constant(0, Type);
1487  }
1488 
1489  DigitVal = Digit;
1490  Val = Val * RadixVal + DigitVal;
1491  }
1492 
1493  // FIXME: Actually do the check for overflow.
1494  if (HasMinus)
1495  Val = -Val;
1496 
1497  if (Type < Val.getBitWidth())
1498  Val=Val.trunc(Type);
1499  else if (Type > Val.getBitWidth())
1500  Val=Val.zext(Type);
1501 
1502  return ExprResult(Builder->Constant(Val));
1503 }
1504 
1508 TypeResult ParserImpl::ParseTypeSpecifier() {
1509  assert(Tok.kind == Token::KWWidth && "Unexpected token.");
1510 
1511  // FIXME: Need APInt technically.
1512  int width = atoi(std::string(Tok.start+1,Tok.length-1).c_str());
1513  ConsumeToken();
1514 
1515  // FIXME: We should impose some sort of maximum just for sanity?
1516  return TypeResult(width);
1517 }
1518 
1519 void ParserImpl::Error(const char *Message, const Token &At) {
1520  ++NumErrors;
1521  if (MaxErrors && NumErrors >= MaxErrors)
1522  return;
1523 
1524  llvm::errs() << Filename
1525  << ":" << At.line << ":" << At.column
1526  << ": error: " << Message << "\n";
1527 
1528  // Skip carat diagnostics on EOF token.
1529  if (At.kind == Token::EndOfFile)
1530  return;
1531 
1532  // Simple caret style diagnostics.
1533  const char *LineBegin = At.start, *LineEnd = At.start,
1534  *BufferBegin = TheMemoryBuffer->getBufferStart(),
1535  *BufferEnd = TheMemoryBuffer->getBufferEnd();
1536 
1537  // Run line pointers forward and back.
1538  while (LineBegin > BufferBegin &&
1539  LineBegin[-1] != '\r' && LineBegin[-1] != '\n')
1540  --LineBegin;
1541  while (LineEnd < BufferEnd &&
1542  LineEnd[0] != '\r' && LineEnd[0] != '\n')
1543  ++LineEnd;
1544 
1545  // Show the line.
1546  llvm::errs() << std::string(LineBegin, LineEnd) << "\n";
1547 
1548  // Show the caret or squiggly, making sure to print back spaces the
1549  // same.
1550  for (const char *S=LineBegin; S != At.start; ++S)
1551  llvm::errs() << (isspace(*S) ? *S : ' ');
1552  if (At.length > 1) {
1553  for (unsigned i=0; i<At.length; ++i)
1554  llvm::errs() << '~';
1555  } else
1556  llvm::errs() << '^';
1557  llvm::errs() << '\n';
1558 }
1559 
1560 // AST API
1561 // FIXME: Move out of parser.
1562 
1563 Decl::Decl(DeclKind _Kind) : Kind(_Kind) {}
1564 
1566  llvm::outs() << "array " << Root->name
1567  << "[" << Root->size << "]"
1568  << " : " << 'w' << Domain << " -> " << 'w' << Range << " = ";
1569 
1570  if (Root->isSymbolicArray()) {
1571  llvm::outs() << "symbolic\n";
1572  } else {
1573  llvm::outs() << '[';
1574  for (unsigned i = 0, e = Root->size; i != e; ++i) {
1575  if (i)
1576  llvm::outs() << " ";
1577  llvm::outs() << Root->constantValues[i];
1578  }
1579  llvm::outs() << "]\n";
1580  }
1581 }
1582 
1584  const ExprHandle *ValuesBegin = 0, *ValuesEnd = 0;
1585  const Array * const* ObjectsBegin = 0, * const* ObjectsEnd = 0;
1586  if (!Values.empty()) {
1587  ValuesBegin = &Values[0];
1588  ValuesEnd = ValuesBegin + Values.size();
1589  }
1590  if (!Objects.empty()) {
1591  ObjectsBegin = &Objects[0];
1592  ObjectsEnd = ObjectsBegin + Objects.size();
1593  }
1594  ExprPPrinter::printQuery(llvm::outs(), ConstraintManager(Constraints),
1595  Query, ValuesBegin, ValuesEnd,
1596  ObjectsBegin, ObjectsEnd,
1597  false);
1598 }
1599 
1600 // Public parser API
1601 
1603 }
1604 
1606 }
1607 
1608 Parser *Parser::Create(const std::string Filename,
1609  const MemoryBuffer *MB,
1610  ExprBuilder *Builder) {
1611  ParserImpl *P = new ParserImpl(Filename, MB, Builder);
1612  P->Initialize();
1613  return P;
1614 }
const unsigned Domain
Domain - The width of indices.
Definition: Parser.h:83
bool isSymbolicArray() const
Definition: Expr.h:641
unsigned line
The length of the token.
Definition: Lexer.h:55
unsigned size
Definition: Expr.h:605
ExprBuilder - Base expression builder class.
Definition: ExprBuilder.h:17
const std::vector< ref< ConstantExpr > > constantValues
Definition: Expr.h:610
const unsigned Range
Range - The width of array contents.
Definition: Parser.h:86
Class representing a complete list of updates into an array.
Definition: Expr.h:655
unsigned length
The beginning of the token string.
Definition: Lexer.h:54
virtual void dump()
dump - Dump the AST node to stderr.
Definition: Parser.cpp:1583
Class representing symbolic expressions.
Definition: Expr.h:88
virtual Width getWidth() const =0
MacroKind
Definition: Parser.cpp:778
const std::string Name
Definition: Parser.h:32
const char * start
The token kind.
Definition: Lexer.h:53
static bool LookupExprInfo(const Token &Tok, unsigned &Kind, bool &IsFixed, int &NumArgs)
Definition: Parser.cpp:796
Decl - Base class for top level declarations.
Definition: Parser.h:41
Lexer - Interface for lexing tokens from a .pc language file.
Definition: Lexer.h:76
static Parser * Create(const std::string Name, const llvm::MemoryBuffer *MB, ExprBuilder *Builder)
Definition: Parser.cpp:1608
const std::string name
Definition: Expr.h:603
virtual ~Parser()
Definition: Parser.cpp:1605
unsigned column
The line number of the start of this token.
Definition: Lexer.h:56
unsigned Width
The type of an expression is simply its width, in bits.
Definition: Expr.h:94
Identifier - Wrapper for a uniqued string.
Definition: Parser.h:31
virtual void dump()
dump - Dump the AST node to stderr.
Definition: Parser.cpp:1565
bool isKeyword() const
isKeyword - True if this token is a keyword.
Definition: Lexer.h:67
#define SetOK(kind, isfixed, numargs)
Parser - Public interface for parsing a .pc language file.
Definition: Parser.h:206
static void printQuery(llvm::raw_ostream &os, const ConstraintManager &constraints, const ref< Expr > &q, const ref< Expr > *evalExprsBegin=0, const ref< Expr > *evalExprsEnd=0, const Array *const *evalArraysBegin=0, const Array *const *evalArraysEnd=0, bool printArrayDecls=true)