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:
self()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>
traverse(T * & E,typename R::R_Ctx Ctx)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.
traverseSExpr(SExpr * E,typename R::R_Ctx Ctx)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.
traverseByCase(SExpr * E,typename R::R_Ctx Ctx)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.
subExprCtx(R_Ctx Ctx)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).
declCtx(R_Ctx Ctx)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).
lazyCtx(R_Ctx Ctx)131   R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; }
132 
133   // Create context for a subexpression that occurs in a type position.
typeCtx(R_Ctx Ctx)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.
Container(CopyReducerBase & S,unsigned N)150     Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {}
151 
152     // Push a new element onto the container.
push_back(T E)153     void push_back(T E) { Elems.push_back(E); }
154 
155     SimpleArray<T> Elems;
156   };
157 
CopyReducerBase(MemRegionRef A)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 
Container(VisitReducerBase & S,unsigned N)176     Container(VisitReducerBase &S, unsigned N) {}
177 
push_back(bool E)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:
reduceNull()191   R_SExpr reduceNull() { return true; }
reduceUndefined(Undefined & Orig)192   R_SExpr reduceUndefined(Undefined &Orig) { return true; }
reduceWildcard(Wildcard & Orig)193   R_SExpr reduceWildcard(Wildcard &Orig) { return true; }
194 
reduceLiteral(Literal & Orig)195   R_SExpr reduceLiteral(Literal &Orig) { return true; }
196   template<class T>
reduceLiteralT(LiteralT<T> & Orig)197   R_SExpr reduceLiteralT(LiteralT<T> &Orig) { return true; }
reduceLiteralPtr(Literal & Orig)198   R_SExpr reduceLiteralPtr(Literal &Orig) { return true; }
199 
reduceFunction(Function & Orig,Variable * Nvd,R_SExpr E0)200   R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
201     return Nvd && E0;
202   }
203 
reduceSFunction(SFunction & Orig,Variable * Nvd,R_SExpr E0)204   R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
205     return Nvd && E0;
206   }
207 
reduceCode(Code & Orig,R_SExpr E0,R_SExpr E1)208   R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
209     return E0 && E1;
210   }
211 
reduceField(Field & Orig,R_SExpr E0,R_SExpr E1)212   R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) {
213     return E0 && E1;
214   }
215 
reduceApply(Apply & Orig,R_SExpr E0,R_SExpr E1)216   R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
217     return E0 && E1;
218   }
219 
reduceSApply(SApply & Orig,R_SExpr E0,R_SExpr E1)220   R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
221     return E0 && E1;
222   }
223 
reduceProject(Project & Orig,R_SExpr E0)224   R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; }
reduceCall(Call & Orig,R_SExpr E0)225   R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; }
reduceAlloc(Alloc & Orig,R_SExpr E0)226   R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; }
reduceLoad(Load & Orig,R_SExpr E0)227   R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; }
reduceStore(Store & Orig,R_SExpr E0,R_SExpr E1)228   R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; }
229 
reduceArrayIndex(Store & Orig,R_SExpr E0,R_SExpr E1)230   R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) {
231     return E0 && E1;
232   }
233 
reduceArrayAdd(Store & Orig,R_SExpr E0,R_SExpr E1)234   R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) {
235     return E0 && E1;
236   }
237 
reduceUnaryOp(UnaryOp & Orig,R_SExpr E0)238   R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
239 
reduceBinaryOp(BinaryOp & Orig,R_SExpr E0,R_SExpr E1)240   R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
241     return E0 && E1;
242   }
243 
reduceCast(Cast & Orig,R_SExpr E0)244   R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
245 
reduceSCFG(SCFG & Orig,Container<BasicBlock * > Bbs)246   R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) {
247     return Bbs.Success;
248   }
249 
reduceBasicBlock(BasicBlock & Orig,Container<R_SExpr> & As,Container<R_SExpr> & Is,R_SExpr T)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 
reducePhi(Phi & Orig,Container<R_SExpr> & As)255   R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
256     return As.Success;
257   }
258 
reduceGoto(Goto & Orig,BasicBlock * B)259   R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) {
260     return true;
261   }
262 
reduceBranch(Branch & O,R_SExpr C,BasicBlock * B0,BasicBlock * B1)263   R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
264     return C;
265   }
266 
reduceReturn(Return & O,R_SExpr E)267   R_SExpr reduceReturn(Return &O, R_SExpr E) {
268     return E;
269   }
270 
reduceIdentifier(Identifier & Orig)271   R_SExpr reduceIdentifier(Identifier &Orig) {
272     return true;
273   }
274 
reduceIfThenElse(IfThenElse & Orig,R_SExpr C,R_SExpr T,R_SExpr E)275   R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) {
276     return C && T && E;
277   }
278 
reduceLet(Let & Orig,Variable * Nvd,R_SExpr B)279   R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) {
280     return Nvd && B;
281   }
282 
enterScope(Variable & Orig,R_SExpr E0)283   Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; }
exitScope(const Variable & Orig)284   void exitScope(const Variable &Orig) {}
enterCFG(SCFG & Cfg)285   void enterCFG(SCFG &Cfg) {}
exitCFG(SCFG & Cfg)286   void exitCFG(SCFG &Cfg) {}
enterBasicBlock(BasicBlock & BB)287   void enterBasicBlock(BasicBlock &BB) {}
exitBasicBlock(BasicBlock & BB)288   void exitBasicBlock(BasicBlock &BB) {}
289 
reduceVariableRef(Variable * Ovd)290   Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
reduceBasicBlockRef(BasicBlock * Obb)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 
visit(SExpr * E)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:
self()312   Self *self() { return reinterpret_cast<Self *>(this); }
313 
314 public:
compareByCase(const SExpr * E1,const SExpr * E2)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 
trueResult()334   CType trueResult() { return true; }
notTrue(CType ct)335   bool notTrue(CType ct) { return !ct; }
336 
compareIntegers(unsigned i,unsigned j)337   bool compareIntegers(unsigned i, unsigned j) { return i == j; }
compareStrings(StringRef s,StringRef r)338   bool compareStrings (StringRef s, StringRef r) { return s == r; }
comparePointers(const void * P,const void * Q)339   bool comparePointers(const void* P, const void* Q) { return P == Q; }
340 
compare(const SExpr * E1,const SExpr * E2)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
enterScope(const Variable * V1,const Variable * V2)348   void enterScope(const Variable *V1, const Variable *V2) {}
leaveScope()349   void leaveScope() {}
350 
compareVariableRefs(const Variable * V1,const Variable * V2)351   bool compareVariableRefs(const Variable *V1, const Variable *V2) {
352     return V1 == V2;
353   }
354 
compareExprs(const SExpr * E1,const SExpr * E2)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 
trueResult()368   CType trueResult() { return true; }
notTrue(CType ct)369   bool notTrue(CType ct) { return !ct; }
370 
compareIntegers(unsigned i,unsigned j)371   bool compareIntegers(unsigned i, unsigned j) { return i == j; }
compareStrings(StringRef s,StringRef r)372   bool compareStrings (StringRef s, StringRef r) { return s == r; }
comparePointers(const void * P,const void * Q)373   bool comparePointers(const void *P, const void *Q) { return P == Q; }
374 
compare(const SExpr * E1,const SExpr * E2)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
enterScope(const Variable * V1,const Variable * V2)386   void enterScope(const Variable* V1, const Variable* V2) {}
leaveScope()387   void leaveScope() {}
388 
compareVariableRefs(const Variable * V1,const Variable * V2)389   bool compareVariableRefs(const Variable* V1, const Variable* V2) {
390     return V1 == V2;
391   }
392 
compareExprs(const SExpr * E1,const SExpr * E2)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)
Verbose(V)418       : Verbose(V), Cleanup(C), CStyle(CS) {}
419 
print(const SExpr * E,StreamType & SS)420   static void print(const SExpr *E, StreamType &SS) {
421     Self printer;
422     printer.printSExpr(E, SS, Prec_MAX);
423   }
424 
425 protected:
self()426   Self *self() { return reinterpret_cast<Self *>(this); }
427 
newline(StreamType & SS)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.
precedence(const SExpr * E)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 
printBlockLabel(StreamType & SS,const BasicBlock * BB,int index)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 
printNull(StreamType & SS)525   void printNull(StreamType &SS) {
526     SS << "#null";
527   }
528 
printFuture(const Future * E,StreamType & SS)529   void printFuture(const Future *E, StreamType &SS) {
530     self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom);
531   }
532 
printUndefined(const Undefined * E,StreamType & SS)533   void printUndefined(const Undefined *E, StreamType &SS) {
534     SS << "#undefined";
535   }
536 
printWildcard(const Wildcard * E,StreamType & SS)537   void printWildcard(const Wildcard *E, StreamType &SS) {
538     SS << "*";
539   }
540 
541   template<class T>
printLiteralT(const LiteralT<T> * E,StreamType & SS)542   void printLiteralT(const LiteralT<T> *E, StreamType &SS) {
543     SS << E->value();
544   }
545 
printLiteralT(const LiteralT<uint8_t> * E,StreamType & SS)546   void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) {
547     SS << "'" << E->value() << "'";
548   }
549 
printLiteral(const Literal * E,StreamType & SS)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 
printLiteralPtr(const LiteralPtr * E,StreamType & SS)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 
printSFunction(const SFunction * E,StreamType & SS)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 
printCode(const Code * E,StreamType & SS)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 
printField(const Field * E,StreamType & SS)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 
printSApply(const SApply * E,StreamType & SS)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 
printProject(const Project * E,StreamType & SS)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 
printCall(const Call * E,StreamType & SS)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 
printAlloc(const Alloc * E,StreamType & SS)743   void printAlloc(const Alloc *E, StreamType &SS) {
744     SS << "new ";
745     self()->printSExpr(E->dataType(), SS, Prec_Other-1);
746   }
747 
printLoad(const Load * E,StreamType & SS)748   void printLoad(const Load *E, StreamType &SS) {
749     self()->printSExpr(E->pointer(), SS, Prec_Postfix);
750     if (!CStyle)
751       SS << "^";
752   }
753 
printStore(const Store * E,StreamType & SS)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 
printArrayIndex(const ArrayIndex * E,StreamType & SS)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 
printArrayAdd(const ArrayAdd * E,StreamType & SS)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 
printUnaryOp(const UnaryOp * E,StreamType & SS)773   void printUnaryOp(const UnaryOp *E, StreamType &SS) {
774     SS << getUnaryOpcodeString(E->unaryOpcode());
775     self()->printSExpr(E->expr(), SS, Prec_Unary);
776   }
777 
printBinaryOp(const BinaryOp * E,StreamType & SS)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 
printCast(const Cast * E,StreamType & SS)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 
printSCFG(const SCFG * E,StreamType & SS)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 
printBBInstr(const SExpr * E,StreamType & SS)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 
printBasicBlock(const BasicBlock * E,StreamType & SS)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 
printPhi(const Phi * E,StreamType & SS)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 
printGoto(const Goto * E,StreamType & SS)875   void printGoto(const Goto *E, StreamType &SS) {
876     SS << "goto ";
877     printBlockLabel(SS, E->targetBlock(), E->index());
878   }
879 
printBranch(const Branch * E,StreamType & SS)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 
printReturn(const Return * E,StreamType & SS)889   void printReturn(const Return *E, StreamType &SS) {
890     SS << "return ";
891     self()->printSExpr(E->returnValue(), SS, Prec_Other);
892   }
893 
printIdentifier(const Identifier * E,StreamType & SS)894   void printIdentifier(const Identifier *E, StreamType &SS) {
895     SS << E->name();
896   }
897 
printIfThenElse(const IfThenElse * E,StreamType & SS)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 
printLet(const Let * E,StreamType & SS)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
932