pointer_closure.h

// This file if part of the llir-opt project.
// Licensing information can be found in the LICENSE file.
// (C) 2018 Nandor Licker. All rights reserved.
 
#pragma once
 
#include <set>
 
#include "core/adt/bitset.h"
#include "core/adt/hash.h"
#include "core/adt/union_find.h"
 
class SymbolicContext;
class SymbolicValue;
class SymbolicPointer;
class SymbolicObject;
class SymbolicHeap;
class SymbolicFrame;
class Func;
class Object;
class CallSite;
 
 
 
class PointerClosure {
public:
  class Node {
  public:
    class node_iterator : public std::iterator
      < std::forward_iterator_tag
      , Node *
      >
    {
    public:
      node_iterator(PointerClosure &graph, BitSet<Node>::iterator it)
        : graph_(graph)
        , it_(it)
      {
      }
 
      bool operator==(const node_iterator &that) const { return it_ == that.it_; }
      bool operator!=(const node_iterator &that) const { return !(*this == that); }
 
      node_iterator &operator++()
      {
        ++it_;
        return *this;
      }
 
      node_iterator operator++(int)
      {
        auto tmp = *this;
        ++*this;
        return tmp;
      }
 
      Node *operator*() const { return graph_.nodes_.Map(*it_); }
      Node *operator->() const { return operator*(); }
 
    private:
      PointerClosure &graph_;
      BitSet<Node>::iterator it_;
    };
 
  public:
    Node(ID<Node> id, PointerClosure &graph) : id_(id), graph_(graph){}
 
    node_iterator nodes_begin() { return node_iterator(graph_, nodes_.begin()); }
    node_iterator nodes_end() { return node_iterator(graph_, nodes_.end()); }
 
    void Union(const Node &that)
    {
      nodes_.Union(that.nodes_);
      self_.Union(that.self_);
      refs_.Union(that.refs_);
      stacks_.Union(that.stacks_);
      funcs_.Union(that.funcs_);
    }
 
  private:
    friend class PointerClosure;
    ID<Node> id_;
    PointerClosure &graph_;
    BitSet<Node> nodes_;
    BitSet<SymbolicObject> self_;
    BitSet<SymbolicObject> refs_;
    BitSet<SymbolicFrame> stacks_;
    BitSet<Func> funcs_;
  };
 
  using func_iterator = BitSet<Func>::iterator;
 
public:
  PointerClosure(SymbolicHeap &heap, SymbolicContext &ctx);
 
  void Add(const SymbolicValue &value);
 
  void AddRead(Object *g);
  void AddWritten(Object *g);
  void AddEscaped(Object *g);
 
  void Add(Func *f);
 
  std::shared_ptr<SymbolicPointer> BuildTainted();
 
  std::shared_ptr<SymbolicPointer> BuildTaint();
 
  Node *GetRoot() { return nodes_.Map(0); }
 
  size_t func_size() const { return funcs_.Size(); }
  func_iterator func_begin() const { return funcs_.begin(); }
  func_iterator func_end() const { return funcs_.end(); }
  llvm::iterator_range<func_iterator> funcs() const
  {
    return llvm::make_range(func_begin(), func_end());
  }
 
private:
  ID<Node> GetNode(ID<SymbolicObject> id);
  ID<Node> GetNode(Object *object);
 
  void Build(ID<Node> id, SymbolicObject &object);
 
  void Compact();
 
private:
  SymbolicHeap &heap_;
  SymbolicContext &ctx_;
 
  UnionFind<Node> nodes_;
  std::unordered_map<ID<SymbolicObject>, ID<Node>> objectToNode_;
 
  std::set<SymbolicObject *> objects_;
  BitSet<SymbolicObject> escapes_;
  BitSet<SymbolicObject> tainted_;
  BitSet<Func> funcs_;
  BitSet<SymbolicFrame> stacks_;
};