symbolic_context.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 <map>
#include <set>
#include <unordered_map>
#include <stack>
 
#include "core/adt/id.h"
#include "passes/pre_eval/symbolic_object.h"
#include "passes/pre_eval/symbolic_frame.h"
 
class Atom;
class Prog;
class Object;
class SymbolicFrame;
class SymbolicSummary;
class CallSite;
 
 
 
class SymbolicContext final {
public:
  class frame_iterator : public std::iterator
    < std::forward_iterator_tag
    , SymbolicFrame *
    >
  {
  public:
    frame_iterator(
        std::vector<unsigned>::const_reverse_iterator it,
        SymbolicContext *ctx)
      : it_(it)
      , ctx_(ctx)
    {
    }
 
    bool operator==(const frame_iterator &that) const { return it_ == that.it_; }
    bool operator!=(const frame_iterator &that) const { return !(*this == that); }
 
    // Pre-increment.
    frame_iterator &operator++()
    {
      it_++;
      return *this;
    }
    // Post-increment
    frame_iterator operator++(int)
    {
      auto tmp = *this;
      ++*this;
      return tmp;
    }
 
    SymbolicFrame &operator*() const { return ctx_->frames_[*it_]; }
    SymbolicFrame *operator->() const { return &operator*(); }
 
  private:
    std::vector<unsigned>::const_reverse_iterator it_;
    SymbolicContext *ctx_;
  };
 
  using ObjectMap = std::unordered_map
      < ID<SymbolicObject>
      , std::unique_ptr<SymbolicObject>
      >;
 
  struct object_iterator : llvm::iterator_adaptor_base
      < object_iterator
      , ObjectMap::const_iterator
      , std::random_access_iterator_tag
      , SymbolicObject *
      >
  {
    explicit object_iterator(ObjectMap::const_iterator it)
      : iterator_adaptor_base(it)
    {
    }
 
    SymbolicObject &operator*() const { return *this->I->second.get(); }
    SymbolicObject *operator->() const { return &operator*(); }
  };
 
public:
  SymbolicContext(SymbolicHeap &heap, SymbolicSummary &state)
    : heap_(heap)
    , state_(state)
  {
  }
 
  SymbolicContext(const SymbolicContext &that);
  ~SymbolicContext();
 
  SymbolicFrame *GetActiveFrame();
  const SymbolicFrame *GetActiveFrame() const
  {
    return const_cast<SymbolicContext *>(this)->GetActiveFrame();
  }
 
  unsigned GetNumArgs() const { return GetActiveFrame()->GetNumArgs(); }
 
  unsigned EnterFrame(Func &func, llvm::ArrayRef<SymbolicValue> args);
  unsigned EnterFrame(llvm::ArrayRef<std::optional<unsigned>> objects);
  void LeaveFrame(Func &func);
  void LeaveRoot();
  bool HasFrame(Func &func);
  void Taint(const SymbolicValue &taint, const SymbolicValue &tainted);
 
  SymbolicObject &GetObject(ID<SymbolicObject> object);
  SymbolicObject &GetObject(Object *object);
  SymbolicObject &GetFrame(unsigned frame, unsigned object)
  {
    return GetObject(frames_[frame].GetObject(object));
  }
 
  SymbolicPointer::Ref Pointer(Atom &atom, int64_t offset);
  SymbolicPointer::Ref Pointer(unsigned frame, unsigned object, int64_t offset);
 
  bool Store(
      const SymbolicPointer &addr,
      const SymbolicValue &val,
      Type type
  );
 
  SymbolicValue Load(const SymbolicPointer &addr, Type type);
 
  SymbolicPointer::Ref Malloc(CallSite &site, std::optional<unsigned> size);
 
  void Merge(const SymbolicContext &that);
 
  std::set<SymbolicFrame *> GetFrames(Func &func);
  DAGFunc &GetSCCFunc(Func &func);
 
  frame_iterator frame_begin()
  {
    return frame_iterator(activeFrames_.rbegin(), this);
  }
  frame_iterator frame_end()
  {
    return frame_iterator(activeFrames_.rend(), this);
  }
  llvm::iterator_range<frame_iterator> frames()
  {
    return llvm::make_range(frame_begin(), frame_end());
  }
 
  object_iterator object_begin() { return object_iterator(objects_.begin()); }
  object_iterator object_end() { return object_iterator(objects_.end()); }
  llvm::iterator_range<object_iterator> objects()
  {
    return llvm::make_range(object_begin(), object_end());
  }
 
private:
  bool StoreExtern(const Extern &e, const SymbolicValue &val, Type ty);
  bool StoreExtern(const Extern &e, int64_t off, const SymbolicValue &val, Type ty);
  SymbolicValue LoadExtern(const Extern &e, Type ty);
  SymbolicValue LoadExtern(const Extern &e, int64_t off, Type ty);
  SymbolicObject *BuildObject(ID<SymbolicObject> id, Object *object);
 
private:
  SymbolicHeap &heap_;
  SymbolicSummary &state_;
 
  std::unordered_map<
      Func *,
      std::shared_ptr<DAGFunc>
  > funcs_;
 
  ObjectMap objects_;
 
  std::vector<SymbolicFrame> frames_;
  std::vector<unsigned> activeFrames_;
  std::optional<SymbolicValue> extern_;
};