Index: doc/theses/fangren_yu_COOP_S20/Report.tex =================================================================== --- doc/theses/fangren_yu_COOP_S20/Report.tex (revision ae450071999426853b0ca05d084ca1a2ae0cfc96) +++ doc/theses/fangren_yu_COOP_S20/Report.tex (revision d1864da6101f2b7824ef52fbb50040da9aeac0c1) @@ -119,7 +119,6 @@ structures. -\paragraph{Declaration nodes} ~ - -\noindent +\subsubsection{Declaration nodes} + A declaration node represents either of: \begin{itemize} @@ -168,7 +167,6 @@ 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,14 +175,12 @@ (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,7 +279,6 @@ 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,4 +300,76 @@ 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 +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 +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 +const node_t * mutate_field(const node_t * node, field_t parent_t::*field, assn_t && val) +\end{C++} +\begin{C++} +template +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 +auto chain_mutate(ptr_base & 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} Index: doc/theses/fangren_yu_COOP_S20/figures/DeepNodeSharing.fig =================================================================== --- doc/theses/fangren_yu_COOP_S20/figures/DeepNodeSharing.fig (revision d1864da6101f2b7824ef52fbb50040da9aeac0c1) +++ doc/theses/fangren_yu_COOP_S20/figures/DeepNodeSharing.fig (revision d1864da6101f2b7824ef52fbb50040da9aeac0c1) @@ -0,0 +1,25 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1800 1950 150 150 1800 1950 1950 1950 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1800 2550 150 150 1800 2550 1950 2550 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2250 1350 150 150 2250 1350 2400 1350 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1350 1350 150 150 1350 1350 1500 1350 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 1350 1500 1800 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2250 1500 1800 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 1800 2100 1800 2400 +4 1 0 50 -1 0 12 0.0000 2 135 210 1350 1425 P1\001 +4 1 0 50 -1 0 12 0.0000 2 135 210 2250 1425 P2\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 1800 2025 A\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 1800 2625 B\001 +4 0 0 50 -1 0 12 0.0000 2 135 675 2100 2625 count: 1\001 +4 0 0 50 -1 0 12 0.0000 2 135 675 2100 2025 count: 2\001 Index: doc/theses/fangren_yu_COOP_S20/figures/DeepNodeSharing.fig.bak =================================================================== --- doc/theses/fangren_yu_COOP_S20/figures/DeepNodeSharing.fig.bak (revision d1864da6101f2b7824ef52fbb50040da9aeac0c1) +++ doc/theses/fangren_yu_COOP_S20/figures/DeepNodeSharing.fig.bak (revision d1864da6101f2b7824ef52fbb50040da9aeac0c1) @@ -0,0 +1,23 @@ +#FIG 3.2 Produced by xfig version 3.2.5c +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1800 1950 150 150 1800 1950 1950 1950 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1800 2550 150 150 1800 2550 1950 2550 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2250 1350 150 150 2250 1350 2400 1350 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 1350 1350 150 150 1350 1350 1500 1350 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 1350 1500 1800 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2250 1500 1800 1800 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 1800 2100 1800 2400 +4 1 0 50 -1 0 12 0.0000 2 135 210 1350 1425 P1\001 +4 1 0 50 -1 0 12 0.0000 2 135 210 2250 1425 P2\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 1800 2025 A\001 +4 1 0 50 -1 0 12 0.0000 2 135 135 1800 2625 B\001