Changeset d1864da for doc/theses/fangren_yu_COOP_S20

Timestamp:

Sep 13, 2020, 10:42:01 PM (4 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

a75d464

Parents:

ae45007

Message:

continue latex version of Fangren's co-op report

Location:

doc/theses/fangren_yu_COOP_S20

Files:

• Report.tex (modified) (5 diffs)
• figures/DeepNodeSharing.fig (added)
• figures/DeepNodeSharing.fig.bak (added)

doc/theses/fangren_yu_COOP_S20/Report.tex

@@ -119 +119 @@
 structures.
 
-\paragraph{Declaration nodes} ~
-
-\noindent
+\subsubsection{Declaration nodes}
+
 A declaration node represents either of:
 \begin{itemize}
@@ -168 +167 @@
 parameters and assertions is the following declaration.
 
-\paragraph{Type nodes} ~
-
-\noindent
+\subsubsection{Type nodes}
+
 A type node represents the type of an object or expression.
 Named types reference the corresponding type declarations. The type of a function is its
@@ -177 +175 @@
 (actual parameter types).
 
-\paragraph{Statement nodes} ~
-
-\noindent
+\subsubsection{Statement nodes}
+
 Statement nodes represent the statements in the program, including basic expression
 statements, control flows and blocks.
 Local declarations (within a block statement) are represented as declaration statements.
 
-\paragraph{Expression nodes} ~
-
-\noindent
+\subsubsection{Expression nodes}
+
 Some expressions are represented differently in the compiler before and after resolution
 stage:
@@ -283 +279 @@
 discussed near the end of this section.
 
-\paragraph{Source: AST/Node.hpp} ~
-
-\noindent
+\subsubsection{Source: AST/Node.hpp}
+
 class @ast::Node@ is the base class of all new-ast node classes, which implements
 reference counting mechanism. Two different counters are recorded: ``strong'' reference
@@ -305 +300 @@
 pointers.
 
+\begin{C++}
+void ast::Node::increment(ref_type ref)
+\end{C++}
+Increments this node's strong or weak reference count.
+\begin{C++}
+void ast::Node::decrement(ref_type ref, bool do_delete = true)
+\end{C++}
+Decrements this node's strong or weak reference count. If strong reference count reaches
+zero, the node is deleted by default.
+\textbf{NOTE}: Setting @do_delete@ to false may result in a detached node. Subsequent code should
+manually delete the node or assign it to a strong pointer to prevent memory leak.
+Reference counting functions are internally called by @ast::ptr_base@.
+\begin{C++}
+template<typename node_t>
+node_t * shallowCopy(const node_t * node)
+\end{C++}
+Returns a mutable, shallow copy of node: all child pointers are pointing to the same child
+nodes.
+\begin{C++}
+template<typename node_t>
+node_t * mutate(const node_t * node)
+\end{C++}
+If node is unique (strong reference count is 1), returns a mutable pointer to the same node.
+Otherwise, returns shallowCopy(node).
+It is an error to mutate a shared node that is weak-referenced. Currently this does not
+happen. The problem may appear once weak pointers to shared nodes (e.g. expression
+nodes) are used; special care will be needed.
+
+\textbf{NOTE}: This naive uniqueness check may not be sufficient in some cases. A discussion of the
+issue is presented at the end of this section.
+\begin{C++}
+template<typename node_t, typename parent_t, typename field_t, typename assn_t>
+const node_t * mutate_field(const node_t * node, field_t parent_t::*field, assn_t && val)
+\end{C++}
+\begin{C++}
+template<typename node_t, typename parent_t, typename coll_t, typename ind_t,
+                typename field_t>
+const node_t * mutate_field_index(const node_t * node, coll_t parent_t::* field, ind_t i,
+                field_t && val)
+\end{C++}
+Helpers for mutating a field on a node using pointer to member (creates shallow copy
+when necessary).
+
+\subsubsection{Issue: Undetected sharing}
+
+The @mutate@ behavior described above has a problem: deeper shared nodes may be
+mistakenly considered as unique. \VRef[Figure]{f:DeepNodeSharing} shows how the problem could arise:
+\begin{figure}
+\centering
+\input{DeepNodeSharing}
+\caption{Deep sharing of nodes}
+\label{f:DeepNodeSharing}
+\end{figure}
+Suppose that we are working on the tree rooted at P1, which
+is logically the chain P1-A-B and P2 is irrelevant, and then
+mutate(B) is called. The algorithm considers B as unique since
+it is only directly owned by A. However, the other tree P2-A-B
+indirectly shares the node B and is therefore wrongly mutated.
+
+To partly address this problem, if the mutation is called higher up the tree, a chain
+mutation helper can be used:
+
+\subsubsection{Source: AST/Chain.hpp}
+
+\begin{C++}
+template<typename node_t, Node::ref_type ref_t>
+auto chain_mutate(ptr_base<node_t, ref_t> & base)
+\end{C++}
+This function returns a chain mutator handle which takes pointer-to-member to go down
+the tree while creating shallow copies as necessary; see @struct _chain_mutator@ in the
+source code for details.
+
 \bibliographystyle{plain}
 \bibliography{pl}