contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h

   1 //===- ThreadSafetyTraverse.h -----------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines a framework for doing generic traversals and rewriting
  10 // operations over the Thread Safety TIL.
  11 //
  12 // UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H
  17 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H
  18
  19 #include "clang/AST/Decl.h"
  20 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
  21 #include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
  22 #include "clang/Basic/LLVM.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/Support/Casting.h"
  25 #include <cstdint>
  26 #include <ostream>
  27
  28 namespace clang {
  29 namespace threadSafety {
  30 namespace til {
  31
  32 // Defines an interface used to traverse SExprs.  Traversals have been made as
  33 // generic as possible, and are intended to handle any kind of pass over the
  34 // AST, e.g. visitors, copying, non-destructive rewriting, destructive
  35 // (in-place) rewriting, hashing, typing, etc.
  36 //
  37 // Traversals implement the functional notion of a "fold" operation on SExprs.
  38 // Each SExpr class provides a traverse method, which does the following:
  39 //   * e->traverse(v):
  40 //       // compute a result r_i for each subexpression e_i
  41 //       for (i = 1..n)  r_i = v.traverse(e_i);
  42 //       // combine results into a result for e,  where X is the class of e
  43 //       return v.reduceX(*e, r_1, .. r_n).
  44 //
  45 // A visitor can control the traversal by overriding the following methods:
  46 //   * v.traverse(e):
  47 //       return v.traverseByCase(e), which returns v.traverseX(e)
  48 //   * v.traverseX(e):   (X is the class of e)
  49 //       return e->traverse(v).
  50 //   * v.reduceX(*e, r_1, .. r_n):
  51 //       compute a result for a node of type X
  52 //
  53 // The reduceX methods control the kind of traversal (visitor, copy, etc.).
  54 // They are defined in derived classes.
  55 //
  56 // Class R defines the basic interface types (R_SExpr).
  57 template <class Self, class R>
  58 class Traversal {
  59 public:
  60   Self *self() { return static_cast<Self *>(this); }
  61
  62   // Traverse an expression -- returning a result of type R_SExpr.
  63   // Override this method to do something for every expression, regardless
  64   // of which kind it is.
  65   // E is a reference, so this can be use for in-place updates.
  66   // The type T must be a subclass of SExpr.
  67   template <class T>
  68   typename R::R_SExpr traverse(T* &E, typename R::R_Ctx Ctx) {
  69     return traverseSExpr(E, Ctx);
  70   }
  71
  72   // Override this method to do something for every expression.
  73   // Does not allow in-place updates.
  74   typename R::R_SExpr traverseSExpr(SExpr *E, typename R::R_Ctx Ctx) {
  75     return traverseByCase(E, Ctx);
  76   }
  77
  78   // Helper method to call traverseX(e) on the appropriate type.
  79   typename R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx) {
  80     switch (E->opcode()) {
  81 #define TIL_OPCODE_DEF(X)                                                   \
  82     case COP_##X:                                                           \
  83       return self()->traverse##X(cast<X>(E), Ctx);
  84 #include "ThreadSafetyOps.def"
  85 #undef TIL_OPCODE_DEF
  86     }
  87     return self()->reduceNull();
  88   }
  89
  90 // Traverse e, by static dispatch on the type "X" of e.
  91 // Override these methods to do something for a particular kind of term.
  92 #define TIL_OPCODE_DEF(X)                                                   \
  93   typename R::R_SExpr traverse##X(X *e, typename R::R_Ctx Ctx) {            \
  94     return e->traverse(*self(), Ctx);                                       \
  95   }
  96 #include "ThreadSafetyOps.def"
  97 #undef TIL_OPCODE_DEF
  98 };
  99
 100 // Base class for simple reducers that don't much care about the context.
 101 class SimpleReducerBase {
 102 public:
 103   enum TraversalKind {
 104     // Ordinary subexpressions.
 105     TRV_Normal,
 106
 107     // Declarations (e.g. function bodies).
 108     TRV_Decl,
 109
 110     // Expressions that require lazy evaluation.
 111     TRV_Lazy,
 112
 113     // Type expressions.
 114     TRV_Type
 115   };
 116
 117   // R_Ctx defines a "context" for the traversal, which encodes information
 118   // about where a term appears.  This can be used to encoding the
 119   // "current continuation" for CPS transforms, or other information.
 120   using R_Ctx = TraversalKind;
 121
 122   // Create context for an ordinary subexpression.
 123   R_Ctx subExprCtx(R_Ctx Ctx) { return TRV_Normal; }
 124
 125   // Create context for a subexpression that occurs in a declaration position
 126   // (e.g. function body).
 127   R_Ctx declCtx(R_Ctx Ctx) { return TRV_Decl; }
 128
 129   // Create context for a subexpression that occurs in a position that
 130   // should be reduced lazily.  (e.g. code body).
 131   R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; }
 132
 133   // Create context for a subexpression that occurs in a type position.
 134   R_Ctx typeCtx(R_Ctx Ctx) { return TRV_Type; }
 135 };
 136
 137 // Base class for traversals that rewrite an SExpr to another SExpr.
 138 class CopyReducerBase : public SimpleReducerBase {
 139 public:
 140   // R_SExpr is the result type for a traversal.
 141   // A copy or non-destructive rewrite returns a newly allocated term.
 142   using R_SExpr = SExpr *;
 143   using R_BasicBlock = BasicBlock *;
 144
 145   // Container is a minimal interface used to store results when traversing
 146   // SExprs of variable arity, such as Phi, Goto, and SCFG.
 147   template <class T> class Container {
 148   public:
 149     // Allocate a new container with a capacity for n elements.
 150     Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {}
 151
 152     // Push a new element onto the container.
 153     void push_back(T E) { Elems.push_back(E); }
 154
 155     SimpleArray<T> Elems;
 156   };
 157
 158   CopyReducerBase(MemRegionRef A) : Arena(A) {}
 159
 160 protected:
 161   MemRegionRef Arena;
 162 };
 163
 164 // Base class for visit traversals.
 165 class VisitReducerBase : public SimpleReducerBase {
 166 public:
 167   // A visitor returns a bool, representing success or failure.
 168   using R_SExpr = bool;
 169   using R_BasicBlock = bool;
 170
 171   // A visitor "container" is a single bool, which accumulates success.
 172   template <class T> class Container {
 173   public:
 174     bool Success = true;
 175
 176     Container(VisitReducerBase &S, unsigned N) {}
 177
 178     void push_back(bool E) { Success = Success && E; }
 179   };
 180 };
 181
 182 // Implements a traversal that visits each subexpression, and returns either
 183 // true or false.
 184 template <class Self>
 185 class VisitReducer : public Traversal<Self, VisitReducerBase>,
 186                      public VisitReducerBase {
 187 public:
 188   VisitReducer() = default;
 189
 190 public:
 191   R_SExpr reduceNull() { return true; }
 192   R_SExpr reduceUndefined(Undefined &Orig) { return true; }
 193   R_SExpr reduceWildcard(Wildcard &Orig) { return true; }
 194
 195   R_SExpr reduceLiteral(Literal &Orig) { return true; }
 196   template<class T>
 197   R_SExpr reduceLiteralT(LiteralT<T> &Orig) { return true; }
 198   R_SExpr reduceLiteralPtr(Literal &Orig) { return true; }
 199
 200   R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
 201     return Nvd && E0;
 202   }
 203
 204   R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
 205     return Nvd && E0;
 206   }
 207
 208   R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
 209     return E0 && E1;
 210   }
 211
 212   R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) {
 213     return E0 && E1;
 214   }
 215
 216   R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
 217     return E0 && E1;
 218   }
 219
 220   R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
 221     return E0 && E1;
 222   }
 223
 224   R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; }
 225   R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; }
 226   R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; }
 227   R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; }
 228   R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; }
 229
 230   R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) {
 231     return E0 && E1;
 232   }
 233
 234   R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) {
 235     return E0 && E1;
 236   }
 237
 238   R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
 239
 240   R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
 241     return E0 && E1;
 242   }
 243
 244   R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
 245
 246   R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) {
 247     return Bbs.Success;
 248   }
 249
 250   R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<R_SExpr> &As,
 251                                 Container<R_SExpr> &Is, R_SExpr T) {
 252     return (As.Success && Is.Success && T);
 253   }
 254
 255   R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
 256     return As.Success;
 257   }
 258
 259   R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) {
 260     return true;
 261   }
 262
 263   R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
 264     return C;
 265   }
 266
 267   R_SExpr reduceReturn(Return &O, R_SExpr E) {
 268     return E;
 269   }
 270
 271   R_SExpr reduceIdentifier(Identifier &Orig) {
 272     return true;
 273   }
 274
 275   R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) {
 276     return C && T && E;
 277   }
 278
 279   R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) {
 280     return Nvd && B;
 281   }
 282
 283   Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; }
 284   void exitScope(const Variable &Orig) {}
 285   void enterCFG(SCFG &Cfg) {}
 286   void exitCFG(SCFG &Cfg) {}
 287   void enterBasicBlock(BasicBlock &BB) {}
 288   void exitBasicBlock(BasicBlock &BB) {}
 289
 290   Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
 291   BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; }
 292
 293 public:
 294   bool traverse(SExpr *E, TraversalKind K = TRV_Normal) {
 295     Success = Success && this->traverseByCase(E);
 296     return Success;
 297   }
 298
 299   static bool visit(SExpr *E) {
 300     Self Visitor;
 301     return Visitor.traverse(E, TRV_Normal);
 302   }
 303
 304 private:
 305   bool Success;
 306 };
 307
 308 // Basic class for comparison operations over expressions.
 309 template <typename Self>
 310 class Comparator {
 311 protected:
 312   Self *self() { return reinterpret_cast<Self *>(this); }
 313
 314 public:
 315   bool compareByCase(const SExpr *E1, const SExpr* E2) {
 316     switch (E1->opcode()) {
 317 #define TIL_OPCODE_DEF(X)                                                     \
 318     case COP_##X:                                                             \
 319       return cast<X>(E1)->compare(cast<X>(E2), *self());
 320 #include "ThreadSafetyOps.def"
 321 #undef TIL_OPCODE_DEF
 322     }
 323     return false;
 324   }
 325 };
 326
 327 class EqualsComparator : public Comparator<EqualsComparator> {
 328 public:
 329   // Result type for the comparison, e.g. bool for simple equality,
 330   // or int for lexigraphic comparison (-1, 0, 1).  Must have one value which
 331   // denotes "true".
 332   using CType = bool;
 333
 334   CType trueResult() { return true; }
 335   bool notTrue(CType ct) { return !ct; }
 336
 337   bool compareIntegers(unsigned i, unsigned j) { return i == j; }
 338   bool compareStrings (StringRef s, StringRef r) { return s == r; }
 339   bool comparePointers(const void* P, const void* Q) { return P == Q; }
 340
 341   bool compare(const SExpr *E1, const SExpr* E2) {
 342     if (E1->opcode() != E2->opcode())
 343       return false;
 344     return compareByCase(E1, E2);
 345   }
 346
 347   // TODO -- handle alpha-renaming of variables
 348   void enterScope(const Variable *V1, const Variable *V2) {}
 349   void leaveScope() {}
 350
 351   bool compareVariableRefs(const Variable *V1, const Variable *V2) {
 352     return V1 == V2;
 353   }
 354
 355   static bool compareExprs(const SExpr *E1, const SExpr* E2) {
 356     EqualsComparator Eq;
 357     return Eq.compare(E1, E2);
 358   }
 359 };
 360
 361 class MatchComparator : public Comparator<MatchComparator> {
 362 public:
 363   // Result type for the comparison, e.g. bool for simple equality,
 364   // or int for lexigraphic comparison (-1, 0, 1).  Must have one value which
 365   // denotes "true".
 366   using CType = bool;
 367
 368   CType trueResult() { return true; }
 369   bool notTrue(CType ct) { return !ct; }
 370
 371   bool compareIntegers(unsigned i, unsigned j) { return i == j; }
 372   bool compareStrings (StringRef s, StringRef r) { return s == r; }
 373   bool comparePointers(const void *P, const void *Q) { return P == Q; }
 374
 375   bool compare(const SExpr *E1, const SExpr *E2) {
 376     // Wildcards match anything.
 377     if (E1->opcode() == COP_Wildcard || E2->opcode() == COP_Wildcard)
 378       return true;
 379     // otherwise normal equality.
 380     if (E1->opcode() != E2->opcode())
 381       return false;
 382     return compareByCase(E1, E2);
 383   }
 384
 385   // TODO -- handle alpha-renaming of variables
 386   void enterScope(const Variable* V1, const Variable* V2) {}
 387   void leaveScope() {}
 388
 389   bool compareVariableRefs(const Variable* V1, const Variable* V2) {
 390     return V1 == V2;
 391   }
 392
 393   static bool compareExprs(const SExpr *E1, const SExpr* E2) {
 394     MatchComparator Matcher;
 395     return Matcher.compare(E1, E2);
 396   }
 397 };
 398
 399 // inline std::ostream& operator<<(std::ostream& SS, StringRef R) {
 400 //   return SS.write(R.data(), R.size());
 401 // }
 402
 403 // Pretty printer for TIL expressions
 404 template <typename Self, typename StreamType>
 405 class PrettyPrinter {
 406 private:
 407   // Print out additional information.
 408   bool Verbose;
 409
 410   // Omit redundant decls.
 411   bool Cleanup;
 412
 413   // Print exprs in C-like syntax.
 414   bool CStyle;
 415
 416 public:
 417   PrettyPrinter(bool V = false, bool C = true, bool CS = true)
 418       : Verbose(V), Cleanup(C), CStyle(CS) {}
 419
 420   static void print(const SExpr *E, StreamType &SS) {
 421     Self printer;
 422     printer.printSExpr(E, SS, Prec_MAX);
 423   }
 424
 425 protected:
 426   Self *self() { return reinterpret_cast<Self *>(this); }
 427
 428   void newline(StreamType &SS) {
 429     SS << "\n";
 430   }
 431
 432   // TODO: further distinguish between binary operations.
 433   static const unsigned Prec_Atom = 0;
 434   static const unsigned Prec_Postfix = 1;
 435   static const unsigned Prec_Unary = 2;
 436   static const unsigned Prec_Binary = 3;
 437   static const unsigned Prec_Other = 4;
 438   static const unsigned Prec_Decl = 5;
 439   static const unsigned Prec_MAX = 6;
 440
 441   // Return the precedence of a given node, for use in pretty printing.
 442   unsigned precedence(const SExpr *E) {
 443     switch (E->opcode()) {
 444       case COP_Future:     return Prec_Atom;
 445       case COP_Undefined:  return Prec_Atom;
 446       case COP_Wildcard:   return Prec_Atom;
 447
 448       case COP_Literal:    return Prec_Atom;
 449       case COP_LiteralPtr: return Prec_Atom;
 450       case COP_Variable:   return Prec_Atom;
 451       case COP_Function:   return Prec_Decl;
 452       case COP_SFunction:  return Prec_Decl;
 453       case COP_Code:       return Prec_Decl;
 454       case COP_Field:      return Prec_Decl;
 455
 456       case COP_Apply:      return Prec_Postfix;
 457       case COP_SApply:     return Prec_Postfix;
 458       case COP_Project:    return Prec_Postfix;
 459
 460       case COP_Call:       return Prec_Postfix;
 461       case COP_Alloc:      return Prec_Other;
 462       case COP_Load:       return Prec_Postfix;
 463       case COP_Store:      return Prec_Other;
 464       case COP_ArrayIndex: return Prec_Postfix;
 465       case COP_ArrayAdd:   return Prec_Postfix;
 466
 467       case COP_UnaryOp:    return Prec_Unary;
 468       case COP_BinaryOp:   return Prec_Binary;
 469       case COP_Cast:       return Prec_Atom;
 470
 471       case COP_SCFG:       return Prec_Decl;
 472       case COP_BasicBlock: return Prec_MAX;
 473       case COP_Phi:        return Prec_Atom;
 474       case COP_Goto:       return Prec_Atom;
 475       case COP_Branch:     return Prec_Atom;
 476       case COP_Return:     return Prec_Other;
 477
 478       case COP_Identifier: return Prec_Atom;
 479       case COP_IfThenElse: return Prec_Other;
 480       case COP_Let:        return Prec_Decl;
 481     }
 482     return Prec_MAX;
 483   }
 484
 485   void printBlockLabel(StreamType & SS, const BasicBlock *BB, int index) {
 486     if (!BB) {
 487       SS << "BB_null";
 488       return;
 489     }
 490     SS << "BB_";
 491     SS << BB->blockID();
 492     if (index >= 0) {
 493       SS << ":";
 494       SS << index;
 495     }
 496   }
 497
 498   void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true) {
 499     if (!E) {
 500       self()->printNull(SS);
 501       return;
 502     }
 503     if (Sub && E->block() && E->opcode() != COP_Variable) {
 504       SS << "_x" << E->id();
 505       return;
 506     }
 507     if (self()->precedence(E) > P) {
 508       // Wrap expr in () if necessary.
 509       SS << "(";
 510       self()->printSExpr(E, SS, Prec_MAX);
 511       SS << ")";
 512       return;
 513     }
 514
 515     switch (E->opcode()) {
 516 #define TIL_OPCODE_DEF(X)                                                  \
 517     case COP_##X:                                                          \
 518       self()->print##X(cast<X>(E), SS);                                    \
 519       return;
 520 #include "ThreadSafetyOps.def"
 521 #undef TIL_OPCODE_DEF
 522     }
 523   }
 524
 525   void printNull(StreamType &SS) {
 526     SS << "#null";
 527   }
 528
 529   void printFuture(const Future *E, StreamType &SS) {
 530     self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom);
 531   }
 532
 533   void printUndefined(const Undefined *E, StreamType &SS) {
 534     SS << "#undefined";
 535   }
 536
 537   void printWildcard(const Wildcard *E, StreamType &SS) {
 538     SS << "*";
 539   }
 540
 541   template<class T>
 542   void printLiteralT(const LiteralT<T> *E, StreamType &SS) {
 543     SS << E->value();
 544   }
 545
 546   void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) {
 547     SS << "'" << E->value() << "'";
 548   }
 549
 550   void printLiteral(const Literal *E, StreamType &SS) {
 551     if (E->clangExpr()) {
 552       SS << getSourceLiteralString(E->clangExpr());
 553       return;
 554     }
 555     else {
 556       ValueType VT = E->valueType();
 557       switch (VT.Base) {
 558       case ValueType::BT_Void:
 559         SS << "void";
 560         return;
 561       case ValueType::BT_Bool:
 562         if (E->as<bool>().value())
 563           SS << "true";
 564         else
 565           SS << "false";
 566         return;
 567       case ValueType::BT_Int:
 568         switch (VT.Size) {
 569         case ValueType::ST_8:
 570           if (VT.Signed)
 571             printLiteralT(&E->as<int8_t>(), SS);
 572           else
 573             printLiteralT(&E->as<uint8_t>(), SS);
 574           return;
 575         case ValueType::ST_16:
 576           if (VT.Signed)
 577             printLiteralT(&E->as<int16_t>(), SS);
 578           else
 579             printLiteralT(&E->as<uint16_t>(), SS);
 580           return;
 581         case ValueType::ST_32:
 582           if (VT.Signed)
 583             printLiteralT(&E->as<int32_t>(), SS);
 584           else
 585             printLiteralT(&E->as<uint32_t>(), SS);
 586           return;
 587         case ValueType::ST_64:
 588           if (VT.Signed)
 589             printLiteralT(&E->as<int64_t>(), SS);
 590           else
 591             printLiteralT(&E->as<uint64_t>(), SS);
 592           return;
 593         default:
 594           break;
 595         }
 596         break;
 597       case ValueType::BT_Float:
 598         switch (VT.Size) {
 599         case ValueType::ST_32:
 600           printLiteralT(&E->as<float>(), SS);
 601           return;
 602         case ValueType::ST_64:
 603           printLiteralT(&E->as<double>(), SS);
 604           return;
 605         default:
 606           break;
 607         }
 608         break;
 609       case ValueType::BT_String:
 610         SS << "\"";
 611         printLiteralT(&E->as<StringRef>(), SS);
 612         SS << "\"";
 613         return;
 614       case ValueType::BT_Pointer:
 615         SS << "#ptr";
 616         return;
 617       case ValueType::BT_ValueRef:
 618         SS << "#vref";
 619         return;
 620       }
 621     }
 622     SS << "#lit";
 623   }
 624
 625   void printLiteralPtr(const LiteralPtr *E, StreamType &SS) {
 626     SS << E->clangDecl()->getNameAsString();
 627   }
 628
 629   void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) {
 630     if (CStyle && V->kind() == Variable::VK_SFun)
 631       SS << "this";
 632     else
 633       SS << V->name() << V->id();
 634   }
 635
 636   void printFunction(const Function *E, StreamType &SS, unsigned sugared = 0) {
 637     switch (sugared) {
 638       default:
 639         SS << "\\(";   // Lambda
 640         break;
 641       case 1:
 642         SS << "(";     // Slot declarations
 643         break;
 644       case 2:
 645         SS << ", ";    // Curried functions
 646         break;
 647     }
 648     self()->printVariable(E->variableDecl(), SS, true);
 649     SS << ": ";
 650     self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX);
 651
 652     const SExpr *B = E->body();
 653     if (B && B->opcode() == COP_Function)
 654       self()->printFunction(cast<Function>(B), SS, 2);
 655     else {
 656       SS << ")";
 657       self()->printSExpr(B, SS, Prec_Decl);
 658     }
 659   }
 660
 661   void printSFunction(const SFunction *E, StreamType &SS) {
 662     SS << "@";
 663     self()->printVariable(E->variableDecl(), SS, true);
 664     SS << " ";
 665     self()->printSExpr(E->body(), SS, Prec_Decl);
 666   }
 667
 668   void printCode(const Code *E, StreamType &SS) {
 669     SS << ": ";
 670     self()->printSExpr(E->returnType(), SS, Prec_Decl-1);
 671     SS << " -> ";
 672     self()->printSExpr(E->body(), SS, Prec_Decl);
 673   }
 674
 675   void printField(const Field *E, StreamType &SS) {
 676     SS << ": ";
 677     self()->printSExpr(E->range(), SS, Prec_Decl-1);
 678     SS << " = ";
 679     self()->printSExpr(E->body(), SS, Prec_Decl);
 680   }
 681
 682   void printApply(const Apply *E, StreamType &SS, bool sugared = false) {
 683     const SExpr *F = E->fun();
 684     if (F->opcode() == COP_Apply) {
 685       printApply(cast<Apply>(F), SS, true);
 686       SS << ", ";
 687     } else {
 688       self()->printSExpr(F, SS, Prec_Postfix);
 689       SS << "(";
 690     }
 691     self()->printSExpr(E->arg(), SS, Prec_MAX);
 692     if (!sugared)
 693       SS << ")$";
 694   }
 695
 696   void printSApply(const SApply *E, StreamType &SS) {
 697     self()->printSExpr(E->sfun(), SS, Prec_Postfix);
 698     if (E->isDelegation()) {
 699       SS << "@(";
 700       self()->printSExpr(E->arg(), SS, Prec_MAX);
 701       SS << ")";
 702     }
 703   }
 704
 705   void printProject(const Project *E, StreamType &SS) {
 706     if (CStyle) {
 707       // Omit the  this->
 708       if (const auto *SAP = dyn_cast<SApply>(E->record())) {
 709         if (const auto *V = dyn_cast<Variable>(SAP->sfun())) {
 710           if (!SAP->isDelegation() && V->kind() == Variable::VK_SFun) {
 711             SS << E->slotName();
 712             return;
 713           }
 714         }
 715       }
 716       if (isa<Wildcard>(E->record())) {
 717         // handle existentials
 718         SS << "&";
 719         SS << E->clangDecl()->getQualifiedNameAsString();
 720         return;
 721       }
 722     }
 723     self()->printSExpr(E->record(), SS, Prec_Postfix);
 724     if (CStyle && E->isArrow())
 725       SS << "->";
 726     else
 727       SS << ".";
 728     SS << E->slotName();
 729   }
 730
 731   void printCall(const Call *E, StreamType &SS) {
 732     const SExpr *T = E->target();
 733     if (T->opcode() == COP_Apply) {
 734       self()->printApply(cast<Apply>(T), SS, true);
 735       SS << ")";
 736     }
 737     else {
 738       self()->printSExpr(T, SS, Prec_Postfix);
 739       SS << "()";
 740     }
 741   }
 742
 743   void printAlloc(const Alloc *E, StreamType &SS) {
 744     SS << "new ";
 745     self()->printSExpr(E->dataType(), SS, Prec_Other-1);
 746   }
 747
 748   void printLoad(const Load *E, StreamType &SS) {
 749     self()->printSExpr(E->pointer(), SS, Prec_Postfix);
 750     if (!CStyle)
 751       SS << "^";
 752   }
 753
 754   void printStore(const Store *E, StreamType &SS) {
 755     self()->printSExpr(E->destination(), SS, Prec_Other-1);
 756     SS << " := ";
 757     self()->printSExpr(E->source(), SS, Prec_Other-1);
 758   }
 759
 760   void printArrayIndex(const ArrayIndex *E, StreamType &SS) {
 761     self()->printSExpr(E->array(), SS, Prec_Postfix);
 762     SS << "[";
 763     self()->printSExpr(E->index(), SS, Prec_MAX);
 764     SS << "]";
 765   }
 766
 767   void printArrayAdd(const ArrayAdd *E, StreamType &SS) {
 768     self()->printSExpr(E->array(), SS, Prec_Postfix);
 769     SS << " + ";
 770     self()->printSExpr(E->index(), SS, Prec_Atom);
 771   }
 772
 773   void printUnaryOp(const UnaryOp *E, StreamType &SS) {
 774     SS << getUnaryOpcodeString(E->unaryOpcode());
 775     self()->printSExpr(E->expr(), SS, Prec_Unary);
 776   }
 777
 778   void printBinaryOp(const BinaryOp *E, StreamType &SS) {
 779     self()->printSExpr(E->expr0(), SS, Prec_Binary-1);
 780     SS << " " << getBinaryOpcodeString(E->binaryOpcode()) << " ";
 781     self()->printSExpr(E->expr1(), SS, Prec_Binary-1);
 782   }
 783
 784   void printCast(const Cast *E, StreamType &SS) {
 785     if (!CStyle) {
 786       SS << "cast[";
 787       switch (E->castOpcode()) {
 788       case CAST_none:
 789         SS << "none";
 790         break;
 791       case CAST_extendNum:
 792         SS << "extendNum";
 793         break;
 794       case CAST_truncNum:
 795         SS << "truncNum";
 796         break;
 797       case CAST_toFloat:
 798         SS << "toFloat";
 799         break;
 800       case CAST_toInt:
 801         SS << "toInt";
 802         break;
 803       case CAST_objToPtr:
 804         SS << "objToPtr";
 805         break;
 806       }
 807       SS << "](";
 808       self()->printSExpr(E->expr(), SS, Prec_Unary);
 809       SS << ")";
 810       return;
 811     }
 812     self()->printSExpr(E->expr(), SS, Prec_Unary);
 813   }
 814
 815   void printSCFG(const SCFG *E, StreamType &SS) {
 816     SS << "CFG {\n";
 817     for (const auto *BBI : *E)
 818       printBasicBlock(BBI, SS);
 819     SS << "}";
 820     newline(SS);
 821   }
 822
 823   void printBBInstr(const SExpr *E, StreamType &SS) {
 824     bool Sub = false;
 825     if (E->opcode() == COP_Variable) {
 826       const auto *V = cast<Variable>(E);
 827       SS << "let " << V->name() << V->id() << " = ";
 828       E = V->definition();
 829       Sub = true;
 830     }
 831     else if (E->opcode() != COP_Store) {
 832       SS << "let _x" << E->id() << " = ";
 833     }
 834     self()->printSExpr(E, SS, Prec_MAX, Sub);
 835     SS << ";";
 836     newline(SS);
 837   }
 838
 839   void printBasicBlock(const BasicBlock *E, StreamType &SS) {
 840     SS << "BB_" << E->blockID() << ":";
 841     if (E->parent())
 842       SS << " BB_" << E->parent()->blockID();
 843     newline(SS);
 844
 845     for (const auto *A : E->arguments())
 846       printBBInstr(A, SS);
 847
 848     for (const auto *I : E->instructions())
 849       printBBInstr(I, SS);
 850
 851     const SExpr *T = E->terminator();
 852     if (T) {
 853       self()->printSExpr(T, SS, Prec_MAX, false);
 854       SS << ";";
 855       newline(SS);
 856     }
 857     newline(SS);
 858   }
 859
 860   void printPhi(const Phi *E, StreamType &SS) {
 861     SS << "phi(";
 862     if (E->status() == Phi::PH_SingleVal)
 863       self()->printSExpr(E->values()[0], SS, Prec_MAX);
 864     else {
 865       unsigned i = 0;
 866       for (const auto *V : E->values()) {
 867         if (i++ > 0)
 868           SS << ", ";
 869         self()->printSExpr(V, SS, Prec_MAX);
 870       }
 871     }
 872     SS << ")";
 873   }
 874
 875   void printGoto(const Goto *E, StreamType &SS) {
 876     SS << "goto ";
 877     printBlockLabel(SS, E->targetBlock(), E->index());
 878   }
 879
 880   void printBranch(const Branch *E, StreamType &SS) {
 881     SS << "branch (";
 882     self()->printSExpr(E->condition(), SS, Prec_MAX);
 883     SS << ") ";
 884     printBlockLabel(SS, E->thenBlock(), -1);
 885     SS << " ";
 886     printBlockLabel(SS, E->elseBlock(), -1);
 887   }
 888
 889   void printReturn(const Return *E, StreamType &SS) {
 890     SS << "return ";
 891     self()->printSExpr(E->returnValue(), SS, Prec_Other);
 892   }
 893
 894   void printIdentifier(const Identifier *E, StreamType &SS) {
 895     SS << E->name();
 896   }
 897
 898   void printIfThenElse(const IfThenElse *E, StreamType &SS) {
 899     if (CStyle) {
 900       printSExpr(E->condition(), SS, Prec_Unary);
 901       SS << " ? ";
 902       printSExpr(E->thenExpr(), SS, Prec_Unary);
 903       SS << " : ";
 904       printSExpr(E->elseExpr(), SS, Prec_Unary);
 905       return;
 906     }
 907     SS << "if (";
 908     printSExpr(E->condition(), SS, Prec_MAX);
 909     SS << ") then ";
 910     printSExpr(E->thenExpr(), SS, Prec_Other);
 911     SS << " else ";
 912     printSExpr(E->elseExpr(), SS, Prec_Other);
 913   }
 914
 915   void printLet(const Let *E, StreamType &SS) {
 916     SS << "let ";
 917     printVariable(E->variableDecl(), SS, true);
 918     SS << " = ";
 919     printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1);
 920     SS << "; ";
 921     printSExpr(E->body(), SS, Prec_Decl-1);
 922   }
 923 };
 924
 925 class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> {};
 926
 927 } // namespace til
 928 } // namespace threadSafety
 929 } // namespace clang
 930
 931 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H