Changes in / [502ff9e:c341b57]

Files:

• doc/theses/mike_brooks_MMath/array.tex (modified) (1 diff)
• doc/theses/mike_brooks_MMath/string.tex (modified) (2 diffs)
• doc/theses/mike_brooks_MMath/uw-ethesis.tex (modified) (1 diff)
• src/AST/Expr.cpp (modified) (2 diffs)
• src/AST/Expr.hpp (modified) (1 diff)
• src/GenPoly/Box.cpp (modified) (1 diff)
• src/ResolvExpr/CandidateFinder.cpp (modified) (1 diff)
• src/ResolvExpr/ConversionCost.cpp (modified) (1 diff)
• src/ResolvExpr/Cost.hpp (modified) (1 diff)
• src/Validate/EnumAndPointerDecay.cpp (modified) (1 diff)

doc/theses/mike_brooks_MMath/array.tex ¶

@@ -720 +720 @@
         \newcommand{\falsealarm}{{\color{blue}\small{*}}}
         \newcommand{\allowmisuse}{{\color{red}\textbf{!}}}
-        \newcommand{\cmark}{\ding{51}} % from pifont
-        \newcommand{\xmark}{\ding{55}}
 
         \begin{tabular}{@{}l@{\hspace{16pt}}c@{\hspace{8pt}}c@{\hspace{16pt}}c@{\hspace{8pt}}c@{\hspace{16pt}}c}

doc/theses/mike_brooks_MMath/string.tex ¶

@@ -7 +7 @@
 \section{String Operations}
 
-To prepare for the following discussion, a simple comparison among C, \CC, and \CFA basic string operation is presented.
+To prepare for the following discussion, comparisons among C, \CC, Java and \CFA strings are presented, beginning in \VRef[Figure]{f:StrApiCompare}.
+It provides a classic ``cheat sheet'' presentation, summarizing the names of the typical operations.
+
+\begin{figure}
 \begin{cquote}
-\begin{tabular}{@{}l|l|l@{}}
-C @char [ ]@                    &  \CC @string@                 & \CFA @string@ \\
+\begin{tabular}{@{}l|l|l|l@{}}
+C @char [ ]@                    &  \CC @string@                 & Java @String@     & \CFA @string@     \\
 \hline
-@strcpy@, @strncpy@             & @=@                                   & @=@   \\
-@strcat@, @strncat@             & @+@                                   & @+@   \\
-@strcmp@, @strncmp@             & @==@, @!=@, @<@, @<=@, @>@, @>=@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
-@strlen@                                & @length@                              & @size@        \\
-@[ ]@                                   & @[ ]@                                 & @[ ]@ \\
-                                                & @substr@                              & @substr@      \\
-                                                & @replace@                             & @=@ \emph{(on a substring)}\\
-@strstr@                                & @find@, @rfind@               & @find@, MISSING \\
-@strcspn@                               & @find_first_of@, @find_last_of@ & @include@, MISSING \\
-@strspn@                                & @find_first_not_of@, @find_last_not_of@ & @exclude@, MISSING \\
-                                                & @c_str@                               & MISSING \\
+@strcpy@, @strncpy@             & @=@                                   & @=@               & @=@       \\
+@strcat@, @strncat@             & @+@                                   & @+@               & @+@       \\
+@strcmp@, @strncmp@             & @==@, @!=@, @<@, @<=@, @>@, @>=@
+                                                & @equals@, @compareTo@
+                                                                                                                    & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
+@strlen@                                & @length@, @size@              & @length@                      & @size@        \\
+@[ ]@                                   & @[ ]@                                 & @charAt@          & @[ ]@     \\
+@strncpy@                               & @substr@                              & @substring@       & @( )@     \\
+@strncpy@                               & @replace@                             & @replace@         & @=@ \emph{(on a substring)}\\
+@strstr@                                & @find@                                & @indexOf@         & @find@ \\
+@strcspn@                               & @find_first_of@               & @matches@         & @include@ \\
+@strspn@                                & @find_first_not_of@   & @matches@         & @exclude@ \\
+n/a                                             & @c_str@, @data@               & n/a               & @strcpy@, @strncpy@ \\
 \end{tabular}
 \end{cquote}
-The key commonality is that operations work on groups of characters for assigning. copying, scanning, and updating.
+\caption{Comparison of languages' strings, API/``cheat-sheet'' perspective.}
+\label{f:StrApiCompare}
+\end{figure}
+
+The key commonality is that operations work on groups of characters for assigning, copying, scanning, and updating.
 Because a C string is null terminated and requires explicit storage management \see{\VRef{s:String}}, most of its group operations are error prone and expensive.
 Most high-level string libraries use a separate length field and specialized storage management to support group operations.
@@ -32 +41 @@
 int open( const char * pathname, int flags );
 string fname{ "test.cc" );
-open( fname.@c_str()@ );
+open( fname.@c_str()@, O_RDONLY );
 \end{cfa}
 The function @c_str@ does not create a new null-terminated C string from the \CC string, as that requires passing ownership of the C string to the caller for eventual deletion.\footnote{
 C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.}
-Instead, each \CC string is null terminator just in case it might be needed for this purpose.
+Instead, each \CC string is null terminated just in case it might be needed for this purpose.
 Providing this backwards compatibility with C has a ubiquitous performance and storage cost.
+
+While \VRef[Figure]{f:StrApiCompare} emphasizes cross-language similarities, it elides differences in how a certain function is used.
+For example, the @replace@ function in \CC performs a modification on its @this@ parameter, while the Java one allocates and returns a new string with the result, leaving @this@ unmodified.
+Generally, Java's @String@ type is immutable.
+Java provides a @StringBuffer@ near-analog that is mutable, but the differences are significant; for example, this class's @substring@ functions still return copies rather than mutable selections.
+
+These more significant differences are summarized in \VRef[Figure]{f:StrSemanticCompare}.  It calls out the consequences of each language taking a different approach on the ``internal'' issues, like storage management and null-terminator interoperability.  The discussion following justifies the figure's yes/no entries.
+
+\begin{figure}
+\begin{tabular}{@{}p{0.5in}p{2in}p{2in}>{\centering\arraybackslash}p{0.2in}>{\centering\arraybackslash}>{\centering\arraybackslash}p{0.2in}>{\centering\arraybackslash}p{0.2in}>{\centering\arraybackslash}p{0.2in}@{}}
+                                        &                       &                       & \multicolumn{4}{c}{\underline{Supports Helpful?}} \\
+                                        & Required      & Helpful       & C                     & \CC           & Java          & \CFA \\
+\hline
+Type abst'n
+                                        & Low-level: A ``string'' type represents a varying amount of text that is communicated with a function as a parameter/return.
+                                                                & High-level: Using a string-typed variable relieves the user of managing a distinct allocation for the text.
+                                                                                        & \xmark        & \cmark        & \cmark        & \cmark \\
+\hline
+\multirow{2}{0.5in}
+{State}
+                                        & \multirow{2}{2in}
+                                        {Fast Initialize: The target receives the characters of the original, but no time is spent copying characters.  The result is one of Alias or Snapshot.}
+                                                                & Alias: The target is a further name for the text in the original; changes made in either variable are visible in both.
+                                                                                        & \cmark        & \cmark        & \xmark        & \cmark \\
+\cline{3-7}
+                                        &
+                                                                & Snapshot: The target (resp.\ source) contains the value of the source at the time of the initialization until the target (resp.\ source) is explicitly changed.
+                                                                                        & \xmark        & \xmark        & \cmark        & \cmark \\
+\hline
+Symmetry
+                                        & Laxed: The target’s type is anything string-like; it may have a different status concerning ownership.
+                                                                & Strict: The target’s type is the same as the original; both strings are equivalent peers concerning ownership.
+                                                                                        & --            & \xmark        & \cmark        & \cmark \\
+\hline
+Referent
+                                        & Variable-Constrained: The target can accept the entire text of the original.
+                                                                & Fragment: The target can accept an arbitrary substring of the original.
+                                                                                        & \xmark        & \xmark        & \cmark        & \cmark
+\end{tabular}
+
+\noindent
+Notes
+\begin{itemize}
+\item
+        All languages support Required in all criteria.
+\item
+        A language gets ``Supports Helpful'' in one criterion if it can do so without sacrificing the Required achievement on all other criteria.
+\item
+        The C ``string'' is @char *@, under the conventions that @<string.h>@ requires.  Symmetry is not applicable to C.
+\item
+        The Java @String@ class is analyzed; its @StringBuffer@ class behaves similarly to @C++@.
+\end{itemize}
+\caption{Comparison of languages' strings, assignment-semantics perspective.}
+\label{f:StrSemanticCompare}
+\end{figure}
+
+In C:
+\begin{cfa}
+char * s1 = ...; // assumed
+char * s2 = s1;  // alias state, variable-constrained referent
+char * s3 = s1 + 2;  // alias state, variable-constrained referent
+\end{cfa}
+The issue of symmetry is trivial for a low-level type, and so, scored as not applicable to C.
+With the type not managing the text buffer, there is no ownership question, \ie nothing done with the @s1@ or @s2@ variables leads to the memory that their text currently occupies becoming reusable.
+While @s3@ is a valid C-string that contains a proper substring of @s1@, the @s3@ technique does not constitue having a fragment referent because null termination implies the substring cannot be chosen arbitrarily; the technique works only for suffixes.
+
+In \CC:
+\begin{cfa}
+string s1 = ...; // assumed
+string & s2 = s1;  // alias state, lax symmetry, variable-constrained referent
+string s3 = s1;  // NOT fast-initialize (strict symmetry, variable-constrained referent)
+string s4 = s1.substr(2,4);  // NOT fast-initialize (strict symmetry, fragment referent)
+string & s5 = s1.substr(2,4);  // memory-use error
+\end{cfa}
+The lax symmetry of the @s2@ technique reflects how the validity of @s2@ depends on the lifetime of @s1@.
+It is common practice in \CC to use the @s2@ technique for parameter passing, but the safest-bet advice has to be that the callee can only use the referenced string for the duration of the call.
+So, when the called function is a constructor, it is typical that the implementation is doing an @s3@-style initialization of a string-object-typed member.
+Exceptions of this pattern are possible, of course, but they represent the programmer taking responsiblity to assure safety where the type system does not.
+The @s4@ initialization is constrained by specification to copy the substring because of @c_str@ being specified to be a null-terminated character run that is not its own allocation.
+TODO: address caveat that @s3@ could be done fast by reference counting in the text area.
+
+
+In Java:
+\begin{cfa}
+String s1 = ...;  // assumed
+String s2 = s1;  // snapshot state, strict symmetry, variable-constrained referent
+String s3 = s1.substring(2,4);  // snapshot state (possible), strict symmetry, fragment referent
+\end{cfa}
+Here, facts about Java's implicit pointers and pointer equality can overcomplicate the picture.
+The further fact of Java's string immutability means that string variables behave as simple values.
+The result in @s2@ is the value of @s1@, and their pointer equality certainly assures that no time is spent copying characters.
+With @s3@, the case for fast-copy is more subtle.
+Certainly, its value is not pointer-equal to @s1@, implying at least a further allocation.
+TODO: finish the fast-copy case.
+Java strings lacking mutation means that aliasing is not possible with the @String@ type.
+Java's @StringBuffer@ provides aliasing, though without supporting symmetric treatment of a fragment referent; as a result, @StringBuffer@ scores as \CC.
+The easy symmetry that the Java string enjoys is aided by Java's garbage collection; Java's @s2@ is doing effectively the operation of \CC's @s2@, though without the consequence to of complicating memory management.
+
+Finally, in \CFA,
+\begin{cfa}
+string s1 = ...; // assumed
+string s2 = s1; // snapshot state, strict symmetry, variable-constrained referent
+string s3 = s1`shareEdits; // alias state, strict symmetry, variable-constrained referent
+string s4 = s1(2,4); // snapshot state, strict symmetry, fragment referent
+string s5 = s1(2,4)`shareEdits; // alias state, strict symmetry, fragment referent
+\end{cfa}
+all helpful criteria of \VRef[Figure]{f:StrSemanticCompare} are satisfied.
+The \CFA string manages storage, handles all assignments, including those of fragment referents, with fast initialization, provides the choice between snapshot and alias semantics, does so symmetrically with one type (which assures text validity according to the lifecycles of the string variables).
+With aliasing, the intuition is that each string is an editor on an open shared document.
+With fragment aliasing, the intuition is that these editor views have been scolled or zoomed to overlapping, but potentially different, ranges.
+
+The remainder of this chapter explains how the \CFA string achieves this usage style.
+
 
 

doc/theses/mike_brooks_MMath/uw-ethesis.tex ¶

@@ -88 +88 @@
 \usepackage{tabularx}
 \usepackage{pifont}
+\newcommand{\cmark}{\ding{51}}
+\newcommand{\xmark}{\ding{55}}
 \usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig}
+\usepackage{multirow}
 \renewcommand\thesubfigure{(\alph{subfigure})}
 

src/AST/Expr.cpp ¶

@@ -301 +301 @@
 // --- OffsetofExpr
 
-OffsetofExpr::OffsetofExpr( const CodeLocation & loc, const Type * ty, const DeclWithType * mem )
-: OffsetofExpr( loc, ty, mem, nullptr ) {}
-
 OffsetofExpr::OffsetofExpr( const CodeLocation & loc, const Type * ty, const DeclWithType * mem, const Type * res )
 : Expr( loc, res ), type( ty ), member( mem ) {
@@ -324 +321 @@
 
 // --- CommaExpr
+
 bool CommaExpr::get_lvalue() const {
         // This is wrong by C, but the current implementation uses it.

src/AST/Expr.hpp ¶

@@ -539 +539 @@
         readonly<DeclWithType> member;
 
-        OffsetofExpr( const CodeLocation & loc, const Type * ty, const DeclWithType * mem );
         OffsetofExpr( const CodeLocation & loc, const Type * ty, const DeclWithType * mem, const Type * res );
 

src/GenPoly/Box.cpp ¶

@@ -2002 +2002 @@
                         new ast::OffsetofExpr( expr->location,
                                 deepCopy( type ),
-                                memberDecl
+                                memberDecl,
+                                getLayoutType( transUnit() )
                         )
                 ) );

src/ResolvExpr/CandidateFinder.cpp ¶

@@ -2150 +2150 @@
 }
 
-const ast::Expr * CandidateFinder::makeEnumOffsetCast( const ast::EnumInstType * src, 
-        const ast::EnumInstType * dst, const ast::Expr * expr, Cost minCost ) {
+const ast::Expr * CandidateFinder::makeEnumOffsetCast( const ast::EnumInstType * src,
+                const ast::EnumInstType * dst, const ast::Expr * expr, Cost minCost ) {
         auto srcDecl = src->base;
         auto dstDecl = dst->base;
 
-        if (srcDecl->name == dstDecl->name) return expr;
-
-        for (auto& dstChild: dstDecl->inlinedDecl) {
+        if ( srcDecl->name == dstDecl->name ) return expr;
+
+        for ( auto& dstChild : dstDecl->inlinedDecl ) {
                 Cost c = castCost(src, dstChild, false, context.symtab, env);
-                ast::CastExpr * castToDst;
-                if (c<minCost) {
-                        unsigned offset = findChildOffset( dstDecl, dstChild.get()->base );
-                        if (offset > 0) {
-                                auto untyped = ast::UntypedExpr::createCall(
-                                        expr->location,
-                                        "?+?",
-                                        { new ast::CastExpr( expr->location,
-                                                expr,
-                                                new ast::BasicType(ast::BasicKind::SignedInt),
-                                                ast::GeneratedFlag::ExplicitCast ),
-                                                ast::ConstantExpr::from_int(expr->location, offset)} );
-                                CandidateFinder finder(context, env);
-                                finder.find( untyped );
-                                CandidateList winners = findMinCost( finder.candidates );
-                                CandidateRef & choice = winners.front();
-                                choice->expr = new ast::CastExpr(expr->location, choice->expr, dstChild, ast::GeneratedFlag::ExplicitCast);
-                                auto destExpr = makeEnumOffsetCast( src, dstChild, choice->expr, minCost );
-                                if ( !destExpr ) continue;
-                                castToDst = new ast::CastExpr( destExpr, dst );
-                        } else {
-                                castToDst = new ast::CastExpr( expr, dst );
-                        }
-                        return castToDst;
+                if ( minCost <= c ) continue;
+                unsigned offset = findChildOffset( dstDecl, dstChild.get()->base );
+                if ( offset <= 0 ) return new ast::CastExpr( expr, dst );
+
+                auto untyped = ast::UntypedExpr::createCall(
+                        expr->location,
+                        "?+?",
+                        { new ast::CastExpr( expr->location,
+                                expr,
+                                new ast::BasicType( ast::BasicKind::SignedInt ),
+                                ast::GeneratedFlag::ExplicitCast ),
+                                ast::ConstantExpr::from_int( expr->location, offset ) } );
+                CandidateFinder finder(context, env);
+                finder.find( untyped );
+                CandidateList winners = findMinCost( finder.candidates );
+                CandidateRef & choice = winners.front();
+                choice->expr = new ast::CastExpr( expr->location, choice->expr, dstChild, ast::GeneratedFlag::ExplicitCast );
+                if ( auto destExpr = makeEnumOffsetCast( src, dstChild, choice->expr, minCost ) ) {
+                        return new ast::CastExpr( destExpr, dst );
                 }
         }

src/ResolvExpr/ConversionCost.cpp ¶

@@ -518 +518 @@
         auto srcDecl = src->base;
         auto dstDecl = dst->base;
-        if (srcDecl->name == dstDecl->name) return Cost::safe;
+        if ( srcDecl->name == dstDecl->name ) return Cost::safe;
         Cost minCost = Cost::infinity;
-        for (auto child: dstDecl->inlinedDecl) {
-                Cost c = enumCastCost(src, child, symtab, env) + Cost::safe;
-                if (c<minCost) minCost = c;
+        for ( auto child : dstDecl->inlinedDecl ) {
+                Cost c = enumCastCost( src, child, symtab, env ) + Cost::safe;
+                if ( c < minCost ) minCost = c;
         }
         return minCost;

src/ResolvExpr/Cost.hpp ¶

@@ -169 +169 @@
 }
 
+inline bool operator<=( const Cost lhs, const Cost rhs ) {
+        return !(rhs < lhs);
+}
+
 inline Cost operator+( const Cost lhs, const Cost rhs ) {
         if ( lhs.all == Cost::infinity || rhs.all == Cost::infinity ) return Cost{ Cost::infinity };

src/Validate/EnumAndPointerDecay.cpp ¶

@@ -48 +48 @@
                 } else if ( auto value = member.as<ast::InlineMemberDecl>() ) {
                         auto targetEnum = symtab.lookupEnum( value->name );
-                        // assert( targetEnum );
                         if (!targetEnum) {
                                 SemanticError(value, "Only another enum is allowed for enum inline syntax ");
                         }
                         const ast::EnumInstType * instType = new ast::EnumInstType(targetEnum);
-                        mut->inlinedDecl.push_back( std::move(instType) );
+                        mut->inlinedDecl.emplace_back( instType );
                         for ( auto enumMember : targetEnum->members ) {
                                 auto enumObject = enumMember.strict_as<ast::ObjectDecl>();