dmd.ob

Flow analysis for Ownership/Borrowing

Authors

Walter Bright

Source: ob.d

  • Declaration

    void oblive(FuncDeclaration funcdecl);

    Perform ownership/borrowing checks for funcdecl. Does not modify the AST, just checks for errors.

  • Declaration

    struct ObState;

    Collect the state information.

    • Declaration

      Array!size_t varStack;

      temporary storage

    • Declaration

      Array!bool mutableStack;

      parallel to varStack[], is type mutable?

    • Declaration

      PtrVarState[] varPool;

      memory pool

  • Declaration

    struct ObNode;

    A node in the function's expression graph, and its edges to predecessors and successors.

    • exp

      Declaration

      Expression exp;

      expression for the node

    • Declaration

      ObNodes preds;

      predecessors

    • Declaration

      ObNodes succs;

      successors

    • Declaration

      ObNode* tryBlock;

      try-finally block we're inside

    • Declaration

      uint index;

      index of this in obnodes

    • gen

      Declaration

      PtrVarState[] gen;

      new states generated for this node

    • Declaration

      PtrVarState[] input;

      variable states on entry to exp

    • Declaration

      PtrVarState[] output;

      variable states on exit to exp

  • Declaration

    enum PtrState: ubyte;

    Pointer variable states:

    Discussion

    Initial state is not known; ignore for now

    Undefined not in a usable state

    T* p = void;

    Owner mutable pointer

    T* p = initializer;

    Borrowed scope mutable pointer, borrowed from [p]

    T* p = initializer; scope T* b = p;

    Readonly scope const pointer, copied from [p]

    T* p = initializer; scope const(T)* cp = p;

    Examples

    T* p = initializer; // p is owner T** pp = &p; // pp borrows from p

    T* p = initialize; // p is owner T* q = p; // transfer: q is owner, p is undefined

  • Declaration

    const(char)* toChars(PtrState state);

  • Declaration

    struct PtrVarState;

    Carries the state of a pointer variable.

    • Declaration

      BitArray deps;

      dependencies

    • Declaration

      PtrState state;

      state the pointer variable is in

    • Declaration

      void print(VarDeclaration[] vars);

    • Declaration

      void depsToBuf(ref OutBuffer buf, const VarDeclaration[] vars);

      Produce a user-readable comma separated string of the dependencies.

      Parameters

      OutBuffer buf

      write resulting string here

      VarDeclaration[] vars

      array from which to get the variable names

  • Declaration

    void setLabelStatementExtraFields(DsymbolTable labtab);

    Set the .extra field for LabelStatements in labtab[].

  • Declaration

    void toObNodes(ref ObNodes obnodes, Statement s);

    Convert statement into ObNodes.

  • Declaration

    void insertFinallyBlockCalls(ref ObNodes obnodes);

    Insert finally block calls when doing a goto from inside a try block to outside. Done after blocks are generated because then we know all the edges of the graph, but before the pred's are computed.

    Parameters

    ObNodes obnodes

    graph of the function

  • Declaration

    void insertFinallyBlockGotos(ref ObNodes obnodes);

    Remove try-finally scaffolding.

    Parameters

    ObNodes obnodes

    nodes for the function

  • Declaration

    void numberNodes(ref ObNodes obnodes);

    Set the index field of each ObNode to its index in the obnodes[] array.

  • Declaration

    void removeUnreachable(ref ObNodes obnodes);

    Remove unreachable nodes and compress them out of obnodes[].

    Parameters

    ObNodes obnodes

    array of nodes

  • Declaration

    void computePreds(ref ObNodes obnodes);

    Compute predecessors.

  • Declaration

    bool isTrackableVar(VarDeclaration v);

    Are we interested in tracking variable v?

  • Declaration

    VarDeclaration isTrackableVarExp(Expression e);

    Are we interested in tracking this expression?

    Return Value

    variable if so, null if not

  • Declaration

    void collectVars(FuncDeclaration funcdecl, out VarDeclarations vars);

    Find the pointer variable declarations in this function, and fill vars with them.

    Parameters

    FuncDeclaration funcdecl

    function we are in

    VarDeclarations vars

    array to fill in

  • Declaration

    void allocDeps(PtrVarState[] pvss);

    Allocate BitArrays in PtrVarState. Can be allocated much more efficiently by subdividing a single large array of bits

  • Declaration

    void allocStates(ref ObState obstate);

    Allocate state variables foreach node.

  • Declaration

    bool isBorrowedPtr(VarDeclaration v);

    Does v meet the definiton of a Borrowed pointer?

    Return Value

    true if it does

  • Declaration

    bool isReadonlyPtr(VarDeclaration v);

    Does v meet the definiton of a Readonly pointer?

    Return Value

    true if it does

  • Declaration

    void genKill(ref ObState obstate, ObNode* ob);

    Compute the gen vector for ob.

  • Declaration

    PtrState toPtrState(VarDeclaration v);

    Determine the state of a variable based on its type and storage class.

  • Declaration

    bool hasPointersToMutableFields(Type t);

    Does type t contain any pointers to mutable?

  • Declaration

    bool hasMutableFields(Type t);

    Does type t have any mutable fields?

  • Declaration

    void doDataFlowAnalysis(ref ObState obstate);

    Do the data flow analysis (i.e. compute the input[] and output[] vectors for each ObNode).

  • Declaration

    void checkObErrors(ref ObState obstate);

    Check for Ownership/Borrowing errors.

  • Declaration

    void readVar(ObNode* ob, const size_t vi, bool mutable, PtrVarState[] gen);

    Read from variable vi. The beginning of the 'scope' of a variable is when it is first read. Hence, when a read is done, instead of when assignment to the variable is done, the O/B rules are enforced. (Also called "non-lexical scoping".)

  • Declaration

    void makeChildrenUndefined(size_t vi, PtrVarState[] gen);

    Recursively make Undefined all who list vi as a dependency

  • Declaration

    void makeUndefined(size_t vi, PtrVarState[] gen);

    Recursively make Undefined vi undefined and all who list vi as a dependency

  • Declaration

    bool isMutableRef(Type t);

    Is type t a reference to a const or a reference to a mutable?