diff options
| -rw-r--r-- | README.md | 7 | ||||
| -rw-r--r-- | chapter22/README.md | 471 | ||||
| -rw-r--r-- | chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java | 2 | ||||
| -rw-r--r-- | chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java | 22 | ||||
| -rw-r--r-- | chapter23/README.md | 406 |
5 files changed, 518 insertions, 390 deletions
@@ -16,8 +16,8 @@ has a minimal syntax that can be parsed with a recursive descent parser. The Sea-of-Nodes is used for machine code generation in these industrial strength systems - but for this demonstration the backend is both difficult and -less important. This repo will eventually target X86 and at least one more -machine with ahead-of-time compilation - but with an eye to JIT compilation. +less important. This repo targets X86, RISC5 and ARM64 at least with +ahead-of-time compilation - but with an eye towards JIT compilation. This repo also is not intended to be a complete language in any sense, and so the backend starts with levering Java: the Evaluator (first appears in Chapter @@ -65,5 +65,4 @@ The Simple language is styled after a subset of C or Java. * [Chapter 19](chapter19/README.md): Instruction selection and portable compilation * [Chapter 20](chapter20/README.md): Graph Coloring Register Allocation * [Chapter 21](chapter21/README.md): Instruction Encodings & ELF -* [Chapter 22](chapter22/README.md): Strings And I/O - +* [Chapter 22](chapter22/README.md): A Simple Hello, World! diff --git a/chapter22/README.md b/chapter22/README.md index 0fdd9d4a..4cae3ee7 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -1,427 +1,130 @@ -# Chapter 22: Strings and I/O - -It's high time for Strings and printing! In this chapter we look at what it -takes to make a nice user-mode string. We are implementing strings in the base -Simple language (except for perhaps some minor Parser shortcuts). This means -we'll need some canonical representation and a library of string functions. +# Chapter 22: A Hello, World! +It's high time for strings and printing! In this chapter we look at what it +takes to make a basic string - not really a full fledged String class, that will +wait for another chapter. You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter20...linear-chapter21) it to the previous chapter. +## Nested Types and Static Fields -## FFI and I/O Calls - -Calling external / FFI functions. -No linker support for getting the correct signature; name `write` has to be singular and unique. - -`{ i32 fd, u8[] buf, i32 len -> i32 } write = "C";` - - - -## Importing name spaces - -Ponder a `struct sys{}` default import struct. - -Includes `sys.io{}` struct with I/O calls. - -Includes `sys.libc{}` with default libc calls. - - -## Unifying Structs and Arrays - -The idea is that structs have fields indexed by names, and arrays have fields -indexed by numbers, and these ideas are compatible with each other. This idea -has been used by the C language for a long time - following a normal struct C -allows an array and can index it with the usual array syntax. - -```java -struct str { - int hash; // A cache of the strings hash code - u32 #; // The array length - u8 []; // Array of bytes -}; - -str X = "abc"; -print(X.hash); // Read the hash field -X[0]=='a'; // Read array element 0 -X#; // Length of the array - -``` - -Here, the field named `#` holds the array length and the field named `[]` is -the actual array, which follows the other fields directly in memory. -Here is another example for variable length array: - -```java -struct vecInt { - u32 size; // Actual number of elements - u32 #; // The array length or capacity - int []; // Array of integers. -}; -``` - -The obvious limit here is that the array cannot be directly resized; it is -literally in the same memory block as the leading fields. Such a `vecInt` can -be *re-allocated* to a new larger `vecInt`, but the original `vecInt` will be -reclaimed - you cannot use the same `vecInt` reference forever. - -Any number of named fields are allowed: - -```java -struct Class { - str className; - str professor; - int time; - int credits; - Class prerequisite; - u16 #; // Limit of 65535 students per class - Student []; -}; -``` - -Or self-reference: - -```java -struct NTree { - Some val; - u8 #; // Length is 0-255 - NTree []; // More NTrees -}; -``` - -The syntax rules are: -- the last field is named `[]` and can be of any type. -- the second-to-last field is named `#` and must be some unsigned integer type - representing the maximum array length. -- may require a leading space in front of ` []` - - - -### Constructors and Arrays - -The allocation includes the array length, and can include a constructor: -`new NTree{val=17;}[2];` - -The constructor is optional, the array length is not. - -Optional function for initializing arrays, allows for write-once final arrays: -`new u8[buffer#,{ u32 idx -> buffer[idx].toUpperCase() }]` - - - -### Changing array max length - -An issue for large numbers of range-checked small arrays is that reserving a -full 4 bytes for array length can substantially increase the array overhead. -Simple allows for arrays to have smaller max lengths, although these are -treated as a different type than arrays with different max lengths. - -```java -struct x0 { u8 #; u8[]; }; // Array limited to 0-255 length -struct x1 { u16 #; u8[]; }; // Array limited to 0-65535 length -struct x2 { u32 #; u8[]; }; // -struct x3 { u64 #; u8[]; }; // - -x0 x = "abc"; // 4 bytes total: [3, 'a', 'b', 'c'] -x1 y = "def"; // 6 bytes total: [3, 0 , 'd', 'e', 'f', 0,]; 1 pad byte to acheieve 2-byte alignment -x = y; // ERROR, "x1 is not x0", no auto-widening -x += y; // OK, 7 bytes total: [6, 'a', 'b', 'c', 'd', 'e', 'f'] -y += x; // OK, 8 bytes total: [6, 0 , 'd', 'e', 'f', 'a', 'b', 'c'] - -x += "VeryLongString.... ....255_chars"; // Runtime RangeCheck - -// Explicit conversion to widen string -y = "" + x; -``` - - -## Methods and Final Fields and Classes - -Methods are simply function values (final fields) declared inside a struct that -take an implicit `this` argument. - -Final field declared in the original struct definition are *values* and cannot -change; they are the same for all structs. They get moved out of the struct's -memory footprint and into a *class* - a collection of values from the final -fields. Classes are just plain namespaces and have no concrete implementation; -they are not reified. +Simple now supports nested types - this is a name-space only change, so no new +semantics - just the ability to nest type definitions. ```java -struct vecInt { - // Since "add" is declared with `val` in the original struct definition, - // it is a final field and is moved out of here to the class. - - // Add an element to a vector, possibly returning a new larger vector. - val add = { int e -> - if( size >= # ) return copy(# ? #*2 : 1).add(e); - [size++] = e; - return this; +struct Outer { + struct Inner { + int in; + int pi = 3.14; }; - // Copy 'this' to a new larger size - val copy = { int sz2 -> - val v2 = new vecInt[sz2]; - for( int i=0; i<size; i++ ) - v2[i] = [i]; - v2.size = size; - sys.libc.free(this); // Needs a better Mem Management solution - return v2; - }; - - u32 size; // Actual number of elements - u32 #; // The array length or capacity - int []; // Array of integers. + int out; }; - -val primes = new vecInt[0].add(2).add(3).add(5).add(7); - ``` -Here the `val add` field is a *value* field, a constant function value. It is -moved out of the basic `vecInt` object into `vecInt`'s *class*, and takes no -storage space in `vecInt` objects. The same happens for `copy`. The size of a -`vecInt` is thus 2 `u32` words, plus `#*sizeof(int)`, plus any padding -(probably none here). - -The actual usage of this `vecInt` class differs from other similar classes in -other languages: - -- The data and header object are *inlined*, one level of indirection (and - possible cache miss cost) is avoided. -- The array cannot be resized without resizing the entire object. Once the - array is full, further adds will return a **new** larger `vecInt`. - -Lifetime management to avoid using an older version of `vecInt` awaits a later -chapter. - +Any final field set in the declaration (as opposed to the constructor) is +automatically a "static" field - it is final for all instances, and does not +need to be stored in each instances. Instead one copy is kept in a global +space (not really a *class* object yet) and loaded from there. -### Two flavors of extendable arrays/strings: an extra indirection or not +In this example: +- Instances of the `Outer` class have a single `int` field `out`. +- Instances of the `Inner` class have a single `int` field `in`. +- There exists a `Outer.Inner.pi` field in a global space, with value `3.14`. -With an extra indirection you get e.g. Java `ArrayList` or C++ `Vector`. -Without, then any call which extends the extendable array return a potentially -new object, only growing as needed. +## FFI and I/O Calls -```java -val vec1 = new vecInt[0].add(2); // len=1, capacity=1 -val vec2 = vec1.add(3); // NEW vecInt returned, only is deleted; len=2; capacity=2; -vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` -vec2[0]; // OK -vec2[1]; // OK -vec2[2]; // Runtime error, AIOOBE -``` +We can now call external / FFI functions, and they are declared like any other +variable except being assigned "C". Here is the binding for the libc `write` +call: +`{ i32 fd, i32 buf, i32 len -> i32 } write = "C";` -## A String Implementation +Any final variable assigned as "C" will be considered defined externally. The +syntax of this might change slightly to avoid ambiguity with assign the same +"C" string. -Default strings have names like "str", "cstr", "ustr" or such. +There is no linker support for getting the correct signature or namespace; the +name `write` has to be unique when linking. -Always unicode8 with explicit u8 manipulations. Unicode "characters" will come -as function calls over the base implementation, probably in another string class. -## Default string +## Auto-Import and the "sys." namespace -Efficiently growable via concantenation. Supports a variety of IO/printf functions. -The underlying array can be shared mutable if you ask for this. -The defaults will always be private mutable and read-only shared. +The `sys` import will eventually include libc bindings, and any default library +code including printing support, and probably collections. As of this chapter +it includes minimal libc bindings and an easy print: ```java -struct str { - - // Add a string to the string, possibly growing - val add = { str str -> - val self = this; - for( int i=0; i<str#; i++ ) - self = self.add(str[i]); - return self; - }; - - // Add an char to the string, possibly growing - val add = { u8 e -> - if( len >= # ) return copy(# ? #*2 : 1).add(e); - [size++] = e; - return this; +// top-level default import +struct sys { + // libc bindings + /** https://www.man7.org/linux/man-pages/man2/<libc call>.2.html */ + struct libc { + // fd buf len -> len + { i32 i64 i32 -> i32 } write = "C"; + // addr len prot flags fd off -> void* + { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; + // mmap flags + i32 PROT_EXEC = 4; + i32 PROT_READ = 1; + i32 PROT_WRITE= 2; + i32 PROT_NONE = 0; + i32 MAP_PRIVATE = 2; + i32 MAP_ANON = 32; }; - - // Copy 'this' to a new larger size - val copy = { int sz2 -> - val v2 = new str[sz2]; - for( int i=0; i<len; i++ ) - v2[i] = [i]; - v2.len = len; - sys.libc.free(this); // Needs a better Mem Management solution - return v2; + struct io { + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + i32 len = str#; // cast length to signed + return sys.libc.write(1,ptr,len); + }; }; - - val print { -> sys.libc.write(1/*stdout*/,[]/*array base as argument to C*/,len); return this; } - - u32 len; // In-use size - u32 #; // Max length is 4Gig, although variants can request smaller lengths - u8 []; // Character data -}; -``` - - -### A Final String - -Intended to be a **immutable** string, possibly used as a base for a **secure** -string. This needs to be created all at once, and probably requires a -defensive copy. - -```java -struct sstr { - // Possible static call syntax; no references to "this" - val make { str str -> new sstr[str#,str.at] }; - - // Array contents are immutable. - // Still figuring out good syntax for this. - u8 #; - u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax -}; - -// Construction requires a function that produces the array contents. -// Here we are defining a defensive copy over `buf`. -sstr safe = new sstr[buf.len,{ int idx -> buf[idx]; }]; -sstr safe = sstr.make("abc"); // Defensive copy is made -``` - - -### A Extendable String (aka StringBuilder or StringBuffer) - -This API is intended to be a drop-in for a `StringBuilder` style, and takes an -extra indirection with each usage. - -```java -struct xstr { - str !_str; // The extra indirection is here - val add = { str str -> _str = str.add2(str); }; - val write = { int fd -> _str.write(fd); }; -}; -``` - -### A Unicode String - -This API is intended to support unicode character manipulation over a plain `str` - -```java -struct ustr { - // Assuming idx is at the start of a character, return the character - // as a 32b integer. Returns junk integer if not at a character start. - // For all ASCII strings this will amount to a simple byte load. - // For bytes with high order bits set, this may read 1-4 characters. - val at = { int idx -> ... }; -}; -// Unicode character iterator -struct ucharator { -// Return successive unicode character codes -}; -``` - -### A "C" string - -A zero-terminated string, but the length has to be available directly - -```java -struct cstr { - u8 #; // length including the trailing zero - u8[]; // always ends in a zero byte; suitable for direct passing to C string functions }; ``` -### A "german string": a very short string that can exist in a register +The `sys` import itself is Just Another `struct` like any other; it has fields +and types declared internall. Note that these assignments are all final and in +the struct declaration, hence these are all *static* fields. -Length in memory is 1 byte (3 bits?) of length, then 0-7 chars; max 8 chars. -Fits in a 64 bit register. -```java -struct gstr { // aka germanString, or blend string and register "streg" - u3 #; // Size is 0-7 bytes??? - u8 []; // Up to 7 bytes -} -// Using inlined object (see below). All these strings are short and are -// represented as packed integers in a 64b register. -*gstr prize1 = "gold"; -*gstr prize2 = "silver"; -*gstr prize3 = "bronze"; +## Casting a Pointer to an `i64` -``` +You can now cast a pointer to an i64, although not the other way around. +`i64 ptr = str; // cast array base to i64` -### Main becomes `val main = { str[] args -> ...}` +For arrays, this cast is to the array *base* skipping the `#` length field, and +is suitable for passing to external "C" calls. For structs, this is just the +struct base. -## Structs can be inlined +## Arrays of Constants and Constant Arrays -Structs are normally by-reference, but can be converted to by-value by using -the `*` operator, pronounced "contents of" (this name might be changed to -e.g. `inline`). +The Simple type system now supports the notion of a "constant array" - an array +of fixed constants, stored in the ELF file in the RODATA section. We only +support strings at the parser level: "Hello, World!" makes a `u8[13]` array +containing ASCII bytes. -This is a name-space change only, you cannot take the address of the internal -struct without entirely consuming its lifetime. No "escaping". +A constant version of a non-constant array can be assigned using the `u8[~]` +syntax. ```java -// 2 64-bit words, no other overheads -struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; - -// Current Simple rules: always by-reference -struct ByRef { - Complex c; // 4-byte pointer to a Complex -}; -print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c - -// New behavior: by value (inlining a struct) -// The '*' syntax indicator can be something else, e.g. a keyword "inline" -// I am pronouncing '*' as "contents of" -struct ByValue { - *Complex c; // c is inlined, full 16 bytes into ByValue +// Make a mutable array of ints +int N=4; +i32[] is = new i32[N]; +// Mutate the array +for( int i=0; i<N; i++ ) + is[i] = i*i; +// Function "sum" can read but not write the array +val sum = { i32[~] is -> + int sum = 0; + for( int i=0; i<is#; i++ ) + sum += is[i]; + return sum; }; -print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load - -// Mixing Refs and Struct Values. Basically, a ref can be converted -// to a value by taking the "contents of" the ref, and values cannot -// be *converted* to a ref, although they can be copied over a ref. -ref. c = val.c; // Error, mixing refs and values -ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null -val. c = ref.c; // Error, mixing refs and values -val. c = *ref.c; // Allowed, whole structure copy -ref. c = ref.c; // Allowed, pointer copy -val. c = val.c; // Allowed, whole structure copy. -val *c = val.c; // Error, cannot take "contents of" a value - -// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: -ref.c = val.*c; // Assign into ref.c the "contents of" val.c - -// Arrays of inlined structures -var ary = new *Complex[99]; // Array of 99 Complex objects, inlined - -// Calling methods has the same syntax -ref.c.len(); -val.c.len(); - -// Function arguments use the same typing, so can pass-by-value -val math.sin = { *Complex c -> ... }; // Passes a complex by value -math.sin(ref.*c); // Requires de-reference to pass by value -math.sin(val. c); // Pass by value - +return sum(is); ``` - - -## RoadMap for other chapters - -`&&` and `||` -Drop `int` to `i32`. -Drop `TypeMemPtr` to 4 bytes; using `mmap` to make heap in low 4G. -Add optimistic pass SCCP to `opto` -Default parser for-loop construction, or partial peel. - `for( init; test; next ) body` -becomes: -```java -{ init; // Normal scope entry to bound lifetime of index variable -if( !test ) { // Zero-trip count test - do { - body; - next; - } while( test ); // Exit test at loop bottom by default -} }; -``` +Note that this affects the deep contents of the array, and not the array +variable itself. diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index 2a5900c7..f888a93d 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -9,7 +9,7 @@ public class TypeConAryI extends TypeConAry<int[]> { private static final TypeConAryI I123 = make(new int[]{1,2,3}); public static void gather(ArrayList<Type> ts) { ts.add(I123); } @Override public String str() { return "[i32]"; } - @Override public int alignment() { return 3; } + @Override public int alignment() { return 2; } @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryI)t)._ary); } @Override int hash() { return Arrays.hashCode(_ary); } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 3c228a5b..eddba242 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -32,7 +32,7 @@ public class Chapter22Test { } - @Test public void testJig1() throws IOException { + @Test public void testR5Load() throws IOException { EvalRisc5 R5 = TestRisc5.build("riscv_load", 0, 0, false); int trap = R5.step(100); assertEquals(0,trap); @@ -123,5 +123,25 @@ return cc.cz; assertEquals(0,arm.regs[0]); } + @Test + public void testFinalArray() { + String src = """ +int N=4; +i32[] !is = new i32[N]; +for( int i=0; i<N; i++ ) + is[i] = i*i; +val sum = { i32[~] is -> + int sum=0; + for( int i=0; i<is#; i++ ) + sum += is[i]; + return sum; +}; +return sum(is); +"""; + CodeGen code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals("return Phi(Loop,0,(Phi_sum+.[]));", code._stop.toString()); + assertEquals("14", Eval2.eval(code, 0)); + } + } diff --git a/chapter23/README.md b/chapter23/README.md new file mode 100644 index 00000000..433ecf03 --- /dev/null +++ b/chapter23/README.md @@ -0,0 +1,406 @@ +# Chapter 23: TODO! + + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter20...linear-chapter21) it to the previous chapter. + + + + + + +## Unifying Structs and Arrays + +The idea is that structs have fields indexed by names, and arrays have fields +indexed by numbers, and these ideas are compatible with each other. This idea +has been used by the C language for a long time - following a normal struct C +allows an array and can index it with the usual array syntax. + +```java +struct str { + int hash; // A cache of the strings hash code + u32 #; // The array length + u8 []; // Array of bytes +}; + +str X = "abc"; +print(X.hash); // Read the hash field +X[0]=='a'; // Read array element 0 +X#; // Length of the array + +``` + +Here, the field named `#` holds the array length and the field named `[]` is +the actual array, which follows the other fields directly in memory. +Here is another example for variable length array: + +```java +struct vecInt { + u32 size; // Actual number of elements + u32 #; // The array length or capacity + int []; // Array of integers. +}; +``` + +The obvious limit here is that the array cannot be directly resized; it is +literally in the same memory block as the leading fields. Such a `vecInt` can +be *re-allocated* to a new larger `vecInt`, but the original `vecInt` will be +reclaimed - you cannot use the same `vecInt` reference forever. + +Any number of named fields are allowed: + +```java +struct Class { + str className; + str professor; + int time; + int credits; + Class prerequisite; + u16 #; // Limit of 65535 students per class + Student []; +}; +``` + +Or self-reference: + +```java +struct NTree { + Some val; + u8 #; // Length is 0-255 + NTree []; // More NTrees +}; +``` + +The syntax rules are: +- the last field is named `[]` and can be of any type. +- the second-to-last field is named `#` and must be some unsigned integer type + representing the maximum array length. +- may require a leading space in front of ` []` + + + +### Constructors and Arrays + +The allocation includes the array length, and can include a constructor: +`new NTree{val=17;}[2];` + +The constructor is optional, the array length is not. + +Optional function for initializing arrays, allows for write-once final arrays: +`new u8[buffer#,{ u32 idx -> buffer[idx].toUpperCase() }]` + + + +### Changing array max length + +An issue for large numbers of range-checked small arrays is that reserving a +full 4 bytes for array length can substantially increase the array overhead. +Simple allows for arrays to have smaller max lengths, although these are +treated as a different type than arrays with different max lengths. + +```java +struct x0 { u8 #; u8[]; }; // Array limited to 0-255 length +struct x1 { u16 #; u8[]; }; // Array limited to 0-65535 length +struct x2 { u32 #; u8[]; }; // +struct x3 { u64 #; u8[]; }; // + +x0 x = "abc"; // 4 bytes total: [3, 'a', 'b', 'c'] +x1 y = "def"; // 6 bytes total: [3, 0 , 'd', 'e', 'f', 0,]; 1 pad byte to acheieve 2-byte alignment +x = y; // ERROR, "x1 is not x0", no auto-widening +x += y; // OK, 7 bytes total: [6, 'a', 'b', 'c', 'd', 'e', 'f'] +y += x; // OK, 8 bytes total: [6, 0 , 'd', 'e', 'f', 'a', 'b', 'c'] + +x += "VeryLongString.... ....255_chars"; // Runtime RangeCheck + +// Explicit conversion to widen string +y = "" + x; +``` + + +## Methods and Final Fields and Classes + +Methods are simply function values (final fields) declared inside a struct that +take an implicit `this` argument. + +Final field declared in the original struct definition are *values* and cannot +change; they are the same for all structs. They get moved out of the struct's +memory footprint and into a *class* - a collection of values from the final +fields. Classes are just plain namespaces and have no concrete implementation; +they are not reified. + +```java +struct vecInt { + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Add an element to a vector, possibly returning a new larger vector. + val add = { int e -> + if( size >= # ) return copy(# ? #*2 : 1).add(e); + [size++] = e; + return this; + }; + // Copy 'this' to a new larger size + val copy = { int sz2 -> + val v2 = new vecInt[sz2]; + for( int i=0; i<size; i++ ) + v2[i] = [i]; + v2.size = size; + sys.libc.free(this); // Needs a better Mem Management solution + return v2; + }; + + u32 size; // Actual number of elements + u32 #; // The array length or capacity + int []; // Array of integers. +}; + +val primes = new vecInt[0].add(2).add(3).add(5).add(7); + +``` + +Here the `val add` field is a *value* field, a constant function value. It is +moved out of the basic `vecInt` object into `vecInt`'s *class*, and takes no +storage space in `vecInt` objects. The same happens for `copy`. The size of a +`vecInt` is thus 2 `u32` words, plus `#*sizeof(int)`, plus any padding +(probably none here). + +The actual usage of this `vecInt` class differs from other similar classes in +other languages: + +- The data and header object are *inlined*, one level of indirection (and + possible cache miss cost) is avoided. +- The array cannot be resized without resizing the entire object. Once the + array is full, further adds will return a **new** larger `vecInt`. + +Lifetime management to avoid using an older version of `vecInt` awaits a later +chapter. + + +### Two flavors of extendable arrays/strings: an extra indirection or not + +With an extra indirection you get e.g. Java `ArrayList` or C++ `Vector`. + +Without, then any call which extends the extendable array return a potentially +new object, only growing as needed. + +```java +val vec1 = new vecInt[0].add(2); // len=1, capacity=1 +val vec2 = vec1.add(3); // NEW vecInt returned, only is deleted; len=2; capacity=2; +vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` +vec2[0]; // OK +vec2[1]; // OK +vec2[2]; // Runtime error, AIOOBE +``` + + +## A String Implementation + +Default strings have names like "str", "cstr", "ustr" or such. + +Always unicode8 with explicit u8 manipulations. Unicode "characters" will come +as function calls over the base implementation, probably in another string class. + +## Default string + +Efficiently growable via concantenation. Supports a variety of IO/printf functions. +The underlying array can be shared mutable if you ask for this. +The defaults will always be private mutable and read-only shared. + +```java +struct str { + + // Add a string to the string, possibly growing + val add = { str str -> + val self = this; + for( int i=0; i<str#; i++ ) + self = self.add(str[i]); + return self; + }; + + // Add an char to the string, possibly growing + val add = { u8 e -> + if( len >= # ) return copy(# ? #*2 : 1).add(e); + [size++] = e; + return this; + }; + + // Copy 'this' to a new larger size + val copy = { int sz2 -> + val v2 = new str[sz2]; + for( int i=0; i<len; i++ ) + v2[i] = [i]; + v2.len = len; + sys.libc.free(this); // Needs a better Mem Management solution + return v2; + }; + + val print { -> sys.libc.write(1/*stdout*/,[]/*array base as argument to C*/,len); return this; } + + u32 len; // In-use size + u32 #; // Max length is 4Gig, although variants can request smaller lengths + u8 []; // Character data +}; +``` + + +### A Final String + +Intended to be a **immutable** string, possibly used as a base for a **secure** +string. This needs to be created all at once, and probably requires a +defensive copy. + +```java +struct sstr { + // Possible static call syntax; no references to "this" + val make { str str -> new sstr[str#,str.at] }; + + // Array contents are immutable. + // Still figuring out good syntax for this. + u8 #; + u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax +}; + +// Construction requires a function that produces the array contents. +// Here we are defining a defensive copy over `buf`. +sstr safe = new sstr[buf.len,{ int idx -> buf[idx]; }]; +sstr safe = sstr.make("abc"); // Defensive copy is made +``` + + +### A Extendable String (aka StringBuilder or StringBuffer) + +This API is intended to be a drop-in for a `StringBuilder` style, and takes an +extra indirection with each usage. + +```java +struct xstr { + str !_str; // The extra indirection is here + val add = { str str -> _str = str.add2(str); }; + val write = { int fd -> _str.write(fd); }; +}; +``` + +### A Unicode String + +This API is intended to support unicode character manipulation over a plain `str` + +```java +struct ustr { + // Assuming idx is at the start of a character, return the character + // as a 32b integer. Returns junk integer if not at a character start. + // For all ASCII strings this will amount to a simple byte load. + // For bytes with high order bits set, this may read 1-4 characters. + val at = { int idx -> ... }; +}; +// Unicode character iterator +struct ucharator { +// Return successive unicode character codes +}; +``` + +### A "C" string + +A zero-terminated string, but the length has to be available directly + +```java +struct cstr { + u8 #; // length including the trailing zero + u8[]; // always ends in a zero byte; suitable for direct passing to C string functions +}; +``` + +### A "german string": a very short string that can exist in a register + +Length in memory is 1 byte (3 bits?) of length, then 0-7 chars; max 8 chars. +Fits in a 64 bit register. + +```java +struct gstr { // aka germanString, or blend string and register "streg" + u3 #; // Size is 0-7 bytes??? + u8 []; // Up to 7 bytes +} +// Using inlined object (see below). All these strings are short and are +// represented as packed integers in a 64b register. +*gstr prize1 = "gold"; +*gstr prize2 = "silver"; +*gstr prize3 = "bronze"; + +``` + +### Main becomes `val main = { str[] args -> ...}` + + +## Structs can be inlined + +Structs are normally by-reference, but can be converted to by-value by using +the `*` operator, pronounced "contents of" (this name might be changed to +e.g. `inline`). + +This is a name-space change only, you cannot take the address of the internal +struct without entirely consuming its lifetime. No "escaping". + +```java +// 2 64-bit words, no other overheads +struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; + +// Current Simple rules: always by-reference +struct ByRef { + Complex c; // 4-byte pointer to a Complex +}; +print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c + +// New behavior: by value (inlining a struct) +// The '*' syntax indicator can be something else, e.g. a keyword "inline" +// I am pronouncing '*' as "contents of" +struct ByValue { + *Complex c; // c is inlined, full 16 bytes into ByValue +}; +print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load + +// Mixing Refs and Struct Values. Basically, a ref can be converted +// to a value by taking the "contents of" the ref, and values cannot +// be *converted* to a ref, although they can be copied over a ref. +ref. c = val.c; // Error, mixing refs and values +ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null +val. c = ref.c; // Error, mixing refs and values +val. c = *ref.c; // Allowed, whole structure copy +ref. c = ref.c; // Allowed, pointer copy +val. c = val.c; // Allowed, whole structure copy. +val *c = val.c; // Error, cannot take "contents of" a value + +// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: +ref.c = val.*c; // Assign into ref.c the "contents of" val.c + +// Arrays of inlined structures +var ary = new *Complex[99]; // Array of 99 Complex objects, inlined + +// Calling methods has the same syntax +ref.c.len(); +val.c.len(); + +// Function arguments use the same typing, so can pass-by-value +val math.sin = { *Complex c -> ... }; // Passes a complex by value +math.sin(ref.*c); // Requires de-reference to pass by value +math.sin(val. c); // Pass by value + +``` + + + +## RoadMap for other chapters + +`&&` and `||` +Drop `int` to `i32`. +Drop `TypeMemPtr` to 4 bytes; using `mmap` to make heap in low 4G. +Add optimistic pass SCCP to `opto` +Default parser for-loop construction, or partial peel. + `for( init; test; next ) body` +becomes: +```java +{ init; // Normal scope entry to bound lifetime of index variable +if( !test ) { // Zero-trip count test + do { + body; + next; + } while( test ); // Exit test at loop bottom by default +} }; +``` |