Add c_string type, make extern resolve map char* -> c_string

[Reviewed by David and Tom]

== Background ==

Today, the Chapel compiler has 2 string types: wide string and chpl_string. The
wide string type has a .size field but the regular string type does not (it
follows the C convention of null-terminated string). These two string types
significantly complicate the compiler (especially code generation). In
addition, it's easy to make un-scalable algorithms, since appending a character
to a C string is O(n) instead of O(1).

One day, I'd like to improve the internal representation of Chapel strings, so
that they all include a length field, and so that appending a character to a
string is O(1). While I'm at it, I'd also include the short string
optimization* and a few other performance tricks. I intend to one day create
qio_string that can serve as this implementation of Chapel strings and will
integrate neatly with the I/O system.

Lastly, the current wide string type causes interoperability problems with C
code. Lots of development effort has been put towards improving the story, but
it's still messy, with things like wide strings being lowered to C strings in
the code generator (which would stand in the way of me producing a qio_string
entirely in the runtime).  The latest symptom is that some of the extern block
tests have been failing, because externCResolve converted 'char*' into 'Chapel
string' which is *only* true for the single locale case, since in multilocale,
a Chapel string != a C string.

== How this patch fits in ==

Even when we have a better string type, string literals are still very
important - as are compile-time optimization of string operations (which
generate other string literals). It would add difficulty and complexity to
generate C code using string literals that are not C strings, so while it is
certainly possible, it's not something I'm advocating. Instead, I think that
the compiler should continue to work with C string literals.

At the same time, we need a way to talk about C strings when working with
external (C) functions. The case could be made that the Chapel compiler should
view a C string as c_ptr(c_char), but the Chapel compiler absolutely needs a
way to work with and describe C strings.

== What I did ==

I added c_string as a primitive type to the compiler, and also implemented
support functions for going between Chapel strings and C strings in
SysBasic.chpl. I want these conversions to call routines in the runtime (so
that later I will be able to drop in a better string representation), but
couldn't make them normal extern calls because the target functions have a
different signature depending on whether or not the Chapel string is wide. So,
in addition to adding c_string as a primitive type, I also added the
primitives PRIM_STRING_FROM_C_STRING and PRIM_C_STRING_FROM_STRING. Naturally,
I also created the support functions in the runtime to implement these
primitives with Chapel's current local and wide string representations.

I sprinkled .c_str() and toString() calls into the failing extern block tests
in order to get them to work with this change.

== More details ==
 -- chpl_types.h and chpl_types.c gain functions string_from_c_string,
    wide_string_from_c_string, c_string_from_string, c_string_from_wide_string.
    The C string -> Chapel string functions copy the string (since you
    never know how long C string returned by a C function will be around, and
    because we can expect the Chapel string destructor to free that memory),
    but the Chapel string -> C string functions just return a pointer
    to the string data (matching the current behavior of string arguments
    in extern procs).
 -- primitive.h, primitive.cpp, and expr.cpp get new primitives and their
    implementation: PRIM_STRING_FROM_C_STRING and PRIM_C_STRING_FROM_STRING.
    Their implementation just calls the runtime functions added above...
 -- SysBasic.chpl gets toString(c_string) and string.c_str() that call
    primitive string_from_c_string and c_string_from_string, respectively.
 -- symbol.h and symbol.cpp get gStringC, the default value for a c_string,
    which sets the string to NULL.
 -- type.h and type.cpp get dtStringC, aka c_string, the type of a C string
    (ie const char*).
 -- resolveIntents.cpp learns about dtStringC and to pass it by const in
    (since it is already a pointer...)
 -- externCResolve.cpp is modified to convert char* to the Chapel
    type c_string.

Note that I only arrived at this way of solving the problem after many failed
attempts at keeping the compiler modification limited to adding a new
primitive... It's certainly possible that somebody else will come up with a
more limited patch to solve the same problem. However, I think that adding the
C string type will be important for future work including coercions and
especially string literals automatically being C strings (or automatically
coerced to them).
 
== What remains to be done ==

I think that in the future, all string literals should be of type c_string, and
coercion rules should promote a c_string to a Chapel string (using
PRIM_STRING_FROM_C_STRING) when that needs to happen.  If we don't do that,
things like

  extern C {
    #include <stdio.h>
  }

  printf("%i\n", 17);

won't work (since externCResolve would generate printf taking in a C string and
"%i\n" is a Chapel string).

For now, in this kind of case, you would write

  printf("%i\n".c_str(), 17);

... but once we have coercions between C strings and Chapel strings working,
that string literal could just be a C string. Alternatively, we could have
different rules for string literals and other strings (as in other places in
the compiler) so that string literals can act as either C strings or Chapel
strings.


Another issue is that patch leaves something like
 extern proc foo(x:string);
working the way it did previously - namely, that the compiler will assume that
foo takes in a const char* argument. In the future, we might want that
declaration to mean that foo takes in a Chapel string (probably some kind of
struct or record). In any case having both 
 extern proc foo(x:string);
and
 extern proc foo(x:c_string);
do nearly the same thing is not the end-goal here, but changing the way that
the meaning of extern proc foo(x:string) - if it is necessary - is left as
future work.


A further remaining issue is what behaviour should be expected when calling
.c_str() on a remote wide string. This patch causes an error in such cases
but it would be reasonable to generate a 'get' if we can establish when it
would be safe to free the allocated local string. I believe the best approach
here would be to replace a wide string pointing elsewhere with a local copy of
the string, but it's not even an issue if we always copy strings...


Lastly, it's not really necessary to have both a wide string type and a local
string type. In particular, if strings are copied whenever they are used on
another locale - there is no reason to ever store the locale of a string since
it will be know by the compiler. If strings are not totally copied, but
referenced, when used from another locale, there is little penantly to making
the string type larger and including the locale information, because it will
help with the short string optimization*. So, I anticipate that one day, the
Chapel compiler will only know about two string types: Chapel strings and C
strings.


* The short string optimization is where one stores the string, if it is
short enough, in the space normally required by the string object. An easy
example is if a string were {ptr, length} - that's probably 16 bytes, and many
strings can fit into 16 bytes. So you'd steal a bit from length to
distinguish... and store the string value on top of the pointer and most of
the length if it fits. 



git-svn-id: http://svn.code.sf.net/p/chapel/code/trunk@21932 3a8e244f-b0f2-452b-bcba-4c88e055c3ca