aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/environment.c13
-rw-r--r--src/stdlib/bytes.c8
-rw-r--r--src/stdlib/bytes.h1
-rw-r--r--src/stdlib/datatypes.h17
-rw-r--r--src/stdlib/integers.c20
-rw-r--r--src/stdlib/integers.h2
-rw-r--r--src/stdlib/paths.c18
-rw-r--r--src/stdlib/paths.h1
-rw-r--r--src/stdlib/tables.c22
-rw-r--r--src/stdlib/text.c483
-rw-r--r--src/stdlib/text.h2
-rw-r--r--src/tomo.c62
12 files changed, 477 insertions, 172 deletions
diff --git a/src/environment.c b/src/environment.c
index 6446ed89..53042309 100644
--- a/src/environment.c
+++ b/src/environment.c
@@ -91,10 +91,11 @@ env_t *global_env(bool source_mapping)
)},
{"Byte", Type(ByteType), "Byte_t", "Byte$info", TypedList(ns_entry_t,
{"max", "Byte$max", "Byte"},
+ {"get_bit", "Byte$get_bit", "func(x:Byte, bit_index:Int -> Bool)"},
{"hex", "Byte$hex", "func(byte:Byte, uppercase=yes, prefix=no -> Text)"},
- {"is_between", "Byte$is_between", "func(x:Byte,low:Byte,high:Byte -> Bool)"},
+ {"is_between", "Byte$is_between", "func(x:Byte, low:Byte, high:Byte -> Bool)"},
{"min", "Byte$min", "Byte"},
- {"to", "Byte$to", "func(first:Byte,last:Byte,step:Int8?=none -> func(->Byte?))"},
+ {"to", "Byte$to", "func(first:Byte, last:Byte, step:Int8?=none -> func(->Byte?))"},
)},
{"Int", Type(BigIntType), "Int_t", "Int$info", TypedList(ns_entry_t,
{"abs", "Int$abs", "func(x:Int -> Int)"},
@@ -106,6 +107,7 @@ env_t *global_env(bool source_mapping)
{"divided_by", "Int$divided_by", "func(x,y:Int -> Int)"},
{"factorial", "Int$factorial", "func(x:Int -> Int)"},
{"gcd", "Int$gcd", "func(x,y:Int -> Int)"},
+ {"get_bit", "Int$get_bit", "func(x,bit_index:Int -> Bool)"},
{"hex", "Int$hex", "func(i:Int, digits=0, uppercase=yes, prefix=yes -> Text)"},
{"is_between", "Int$is_between", "func(x:Int,low:Int,high:Int -> Bool)"},
{"is_prime", "Int$is_prime", "func(x:Int,reps=50 -> Bool)"},
@@ -138,6 +140,7 @@ env_t *global_env(bool source_mapping)
{"divided_by", "Int64$divided_by", "func(x,y:Int64 -> Int64)"},
{"gcd", "Int64$gcd", "func(x,y:Int64 -> Int64)"},
{"parse", "Int64$parse", "func(text:Text -> Int64?)"},
+ {"get_bit", "Int64$get_bit", "func(x:Int64, bit_index:Int -> Bool)"},
{"hex", "Int64$hex", "func(i:Int64, digits=0, uppercase=yes, prefix=yes -> Text)"},
{"is_between", "Int64$is_between", "func(x:Int64,low:Int64,high:Int64 -> Bool)"},
{"max", "Int64$max", "Int64"},
@@ -159,6 +162,7 @@ env_t *global_env(bool source_mapping)
{"divided_by", "Int32$divided_by", "func(x,y:Int32 -> Int32)"},
{"gcd", "Int32$gcd", "func(x,y:Int32 -> Int32)"},
{"parse", "Int32$parse", "func(text:Text -> Int32?)"},
+ {"get_bit", "Int32$get_bit", "func(x:Int32, bit_index:Int -> Bool)"},
{"hex", "Int32$hex", "func(i:Int32, digits=0, uppercase=yes, prefix=yes -> Text)"},
{"is_between", "Int32$is_between", "func(x:Int32,low:Int32,high:Int32 -> Bool)"},
{"max", "Int32$max", "Int32"},
@@ -180,6 +184,7 @@ env_t *global_env(bool source_mapping)
{"divided_by", "Int16$divided_by", "func(x,y:Int16 -> Int16)"},
{"gcd", "Int16$gcd", "func(x,y:Int16 -> Int16)"},
{"parse", "Int16$parse", "func(text:Text -> Int16?)"},
+ {"get_bit", "Int16$get_bit", "func(x:Int16, bit_index:Int -> Bool)"},
{"hex", "Int16$hex", "func(i:Int16, digits=0, uppercase=yes, prefix=yes -> Text)"},
{"is_between", "Int16$is_between", "func(x:Int16,low:Int16,high:Int16 -> Bool)"},
{"max", "Int16$max", "Int16"},
@@ -201,6 +206,7 @@ env_t *global_env(bool source_mapping)
{"divided_by", "Int8$divided_by", "func(x,y:Int8 -> Int8)"},
{"gcd", "Int8$gcd", "func(x,y:Int8 -> Int8)"},
{"parse", "Int8$parse", "func(text:Text -> Int8?)"},
+ {"get_bit", "Int8$get_bit", "func(x:Int8, bit_index:Int -> Bool)"},
{"hex", "Int8$hex", "func(i:Int8, digits=0, uppercase=yes, prefix=yes -> Text)"},
{"is_between", "Int8$is_between", "func(x:Int8,low:Int8,high:Int8 -> Bool)"},
{"max", "Int8$max", "Int8"},
@@ -320,6 +326,7 @@ env_t *global_env(bool source_mapping)
{"from_components", "Path$from_components", "func(components:[Text] -> Path)"},
{"glob", "Path$glob", "func(path:Path -> [Path])"},
{"group", "Path$group", "func(path:Path, follow_symlinks=yes -> Text?)"},
+ {"has_extension", "Path$has_extension", "func(path:Path, extension:Text -> Bool)"},
{"is_directory", "Path$is_directory", "func(path:Path, follow_symlinks=yes -> Bool)"},
{"is_file", "Path$is_file", "func(path:Path, follow_symlinks=yes -> Bool)"},
{"is_pipe", "Path$is_pipe", "func(path:Path, follow_symlinks=yes -> Bool)"},
@@ -360,9 +367,11 @@ env_t *global_env(bool source_mapping)
{"from_text", "Path$from_text", "func(text:Text -> Path)"},
{"has", "Text$has", "func(text:Text, target:Text -> Bool)"},
{"join", "Text$join", "func(glue:Text, pieces:[Text] -> Text)"},
+ {"layout", "Text$layout", "func(text:Text -> Text)"},
{"left_pad", "Text$left_pad", "func(text:Text, count:Int, pad=' ', language='C' -> Text)"},
{"lines", "Text$lines", "func(text:Text -> [Text])"},
{"lower", "Text$lower", "func(text:Text, language='C' -> Text)"},
+ {"memory_size", "Text$memory_size", "func(text:Text -> Int)"},
{"middle_pad", "Text$middle_pad", "func(text:Text, count:Int, pad=' ', language='C' -> Text)"},
{"quoted", "Text$quoted", "func(text:Text, color=no, quotation_mark='\"' -> Text)"},
{"repeat", "Text$repeat", "func(text:Text, count:Int -> Text)"},
diff --git a/src/stdlib/bytes.c b/src/stdlib/bytes.c
index b5c10aa2..48c8b93b 100644
--- a/src/stdlib/bytes.c
+++ b/src/stdlib/bytes.c
@@ -49,6 +49,14 @@ public Text_t Byte$hex(Byte_t byte, bool uppercase, bool prefix) {
return text;
}
+public bool Byte$get_bit(Byte_t x, Int_t bit_index) {
+ if (Int$compare_value(bit_index, I(1)) < 0)
+ fail("Invalid bit index (expected 1 or higher): ", bit_index);
+ if (Int$compare_value(bit_index, I(8)) > 0)
+ fail("Bit index is too large! There are only 8 bits in a byte, but index is: ", bit_index);
+ return ((x & (Byte_t)(1L << (Int64$from_int(bit_index, true)-1L))) != 0);
+}
+
#ifdef __TINYC__
#define __builtin_add_overflow(x, y, result) ({ *(result) = (x) + (y); false; })
#endif
diff --git a/src/stdlib/bytes.h b/src/stdlib/bytes.h
index 5c64687d..e733c274 100644
--- a/src/stdlib/bytes.h
+++ b/src/stdlib/bytes.h
@@ -30,5 +30,6 @@ extern const Byte_t Byte$max;
extern const TypeInfo_t Byte$info;
Text_t Byte$hex(Byte_t byte, bool uppercase, bool prefix);
+bool Byte$get_bit(Byte_t x, Int_t bit_index);
// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/src/stdlib/datatypes.h b/src/stdlib/datatypes.h
index c06f7a42..00a9411f 100644
--- a/src/stdlib/datatypes.h
+++ b/src/stdlib/datatypes.h
@@ -8,12 +8,13 @@
#include <stdint.h>
#include <time.h>
-#define LIST_LENGTH_BITS 42
-#define LIST_FREE_BITS 6
+#define LIST_LENGTH_BITS 64
+#define LIST_FREE_BITS 48
+#define LIST_ATOMIC_BITS 1
#define LIST_REFCOUNT_BITS 3
#define LIST_STRIDE_BITS 12
-#define MAX_FOR_N_BITS(N) ((1<<(N))-1)
+#define MAX_FOR_N_BITS(N) ((1L<<(N))-1L)
#define LIST_MAX_STRIDE MAX_FOR_N_BITS(LIST_STRIDE_BITS-1)
#define LIST_MIN_STRIDE (~MAX_FOR_N_BITS(LIST_STRIDE_BITS-1))
#define LIST_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(LIST_REFCOUNT_BITS)
@@ -46,8 +47,8 @@ typedef struct {
// bit arithmetic to extract the necessary values, which is cheaper than
// spilling onto the stack and needing to retrieve data from the stack.
int64_t length:LIST_LENGTH_BITS;
- uint8_t free:LIST_FREE_BITS;
- bool atomic:1;
+ uint64_t free:LIST_FREE_BITS;
+ bool atomic:LIST_ATOMIC_BITS;
uint8_t data_refcount:LIST_REFCOUNT_BITS;
int16_t stride:LIST_STRIDE_BITS;
} List_t;
@@ -77,7 +78,7 @@ typedef struct {
void *fn, *userdata;
} Closure_t;
-enum text_type { TEXT_ASCII, TEXT_GRAPHEMES, TEXT_CONCAT };
+enum text_type { TEXT_ASCII, TEXT_GRAPHEMES, TEXT_CONCAT, TEXT_BLOB };
typedef struct Text_s {
int64_t length:54; // Number of grapheme clusters
@@ -95,6 +96,10 @@ typedef struct Text_s {
struct {
const struct Text_s *left, *right;
};
+ struct {
+ const int32_t *map;
+ const uint8_t *bytes;
+ } blob;
};
} Text_t;
diff --git a/src/stdlib/integers.c b/src/stdlib/integers.c
index 7c623663..018798ec 100644
--- a/src/stdlib/integers.c
+++ b/src/stdlib/integers.c
@@ -359,6 +359,19 @@ public OptionalInt_t Int$sqrt(Int_t i)
return Int$from_mpz(result);
}
+public bool Int$get_bit(Int_t x, Int_t bit_index)
+{
+ mpz_t i;
+ mpz_init_set_int(i, x);
+ if (Int$compare_value(bit_index, I(1)) < 0)
+ fail("Invalid bit index (expected 1 or higher): ", bit_index);
+ if (Int$compare_value(bit_index, Int$from_int64(INT64_MAX)) > 0)
+ fail("Bit index is too large! ", bit_index);
+
+ int is_bit_set = mpz_tstbit(i, (mp_bitcnt_t)(Int64$from_int(bit_index, true)-1));
+ return (bool)is_bit_set;
+}
+
typedef struct {
OptionalInt_t current, last;
Int_t step;
@@ -620,6 +633,13 @@ public void Int32$deserialize(FILE *in, void *outval, List_t *pointers, const Ty
} \
return bit_list; \
} \
+ public bool KindOfInt ## $get_bit(c_type x, Int_t bit_index) { \
+ if (Int$compare_value(bit_index, I(1)) < 0) \
+ fail("Invalid bit index (expected 1 or higher): ", bit_index); \
+ if (Int$compare_value(bit_index, Int$from_int64(sizeof(c_type)*8)) > 0) \
+ fail("Bit index is too large! There are only ", sizeof(c_type)*8, " bits, but index is: ", bit_index); \
+ return ((x & (c_type)(1L << (Int64$from_int(bit_index, true)-1L))) != 0); \
+ } \
typedef struct { \
Optional##KindOfInt##_t current, last; \
KindOfInt##_t step; \
diff --git a/src/stdlib/integers.h b/src/stdlib/integers.h
index 4eaac916..beb26bd6 100644
--- a/src/stdlib/integers.h
+++ b/src/stdlib/integers.h
@@ -29,6 +29,7 @@
Text_t type_name ## $hex(c_type i, Int_t digits, bool uppercase, bool prefix); \
Text_t type_name ## $octal(c_type i, Int_t digits, bool prefix); \
List_t type_name ## $bits(c_type x); \
+ bool type_name ## $get_bit(c_type x, Int_t bit_index); \
Closure_t type_name ## $to(c_type first, c_type last, Optional ## type_name ## _t step); \
Closure_t type_name ## $onward(c_type first, c_type step); \
PUREFUNC Optional ## type_name ## _t type_name ## $parse(Text_t text); \
@@ -105,6 +106,7 @@ Int_t Int$abs(Int_t x);
Int_t Int$power(Int_t base, Int_t exponent);
Int_t Int$gcd(Int_t x, Int_t y);
OptionalInt_t Int$sqrt(Int_t i);
+bool Int$get_bit(Int_t x, Int_t bit_index);
#define BIGGEST_SMALL_INT 0x3fffffff
#define SMALLEST_SMALL_INT -0x40000000
diff --git a/src/stdlib/paths.c b/src/stdlib/paths.c
index 5047d615..94baf995 100644
--- a/src/stdlib/paths.c
+++ b/src/stdlib/paths.c
@@ -372,7 +372,7 @@ public OptionalList_t Path$read_bytes(Path_t path, OptionalInt_t count)
close(fd);
if (count.small != 0 && (int64_t)len < target_count)
fail("Could not read ", target_count, " bytes from ", path, " (only got ", (uint64_t)len, ")");
- return (List_t){.data=content, .atomic=1, .stride=1, .length=len};
+ return (List_t){.data=content, .atomic=1, .stride=1, .length=(int64_t)len};
}
}
@@ -609,6 +609,22 @@ public Text_t Path$extension(Path_t path, bool full)
return Text$from_str(extension);
}
+public bool Path$has_extension(Path_t path, Text_t extension)
+{
+ if (path.components.length < 2)
+ return extension.length == 0;
+
+ Text_t last = *(Text_t*)(path.components.data + path.components.stride*(path.components.length-1));
+
+ if (extension.length == 0)
+ return !Text$has(Text$from(last, I(2)), Text(".")) || Text$equal_values(last, Text(".."));
+
+ if (!Text$starts_with(extension, Text(".")))
+ extension = Texts(Text("."), extension);
+
+ return Text$ends_with(Text$from(last, I(2)), extension);
+}
+
public Path_t Path$child(Path_t path, Text_t name)
{
if (Text$has(name, Text("/")) || Text$has(name, Text(";")))
diff --git a/src/stdlib/paths.h b/src/stdlib/paths.h
index 4f94d3e4..3a9cdef7 100644
--- a/src/stdlib/paths.h
+++ b/src/stdlib/paths.h
@@ -51,6 +51,7 @@ Path_t Path$write_unique_bytes(Path_t path, List_t bytes);
Path_t Path$parent(Path_t path);
Text_t Path$base_name(Path_t path);
Text_t Path$extension(Path_t path, bool full);
+bool Path$has_extension(Path_t path, Text_t extension);
Path_t Path$child(Path_t path, Text_t name);
Path_t Path$sibling(Path_t path, Text_t name);
Path_t Path$with_extension(Path_t path, Text_t extension, bool replace);
diff --git a/src/stdlib/tables.c b/src/stdlib/tables.c
index 762afb06..9301914c 100644
--- a/src/stdlib/tables.c
+++ b/src/stdlib/tables.c
@@ -177,20 +177,16 @@ static void Table$set_bucket(Table_t *t, const void *entry, int32_t index, const
// Move mid-chain entry to free space and update predecessor
buckets[predecessor].next_bucket = t->bucket_info->last_free;
buckets[t->bucket_info->last_free] = *bucket;
- } else { // Collided with the start of a chain
+
+ bucket->occupied = 1;
+ bucket->index = index;
+ bucket->next_bucket = END_OF_CHAIN;
+ } else { // Collided with the start of a chain, put the new entry in chain position #2
hdebug("Hit start of a chain\n");
- uint64_t end_of_chain = hash;
- while (buckets[end_of_chain].next_bucket != END_OF_CHAIN)
- end_of_chain = buckets[end_of_chain].next_bucket;
- hdebug("Appending to chain\n");
- // Chain now ends on the free space:
- buckets[end_of_chain].next_bucket = t->bucket_info->last_free;
- bucket = &buckets[t->bucket_info->last_free];
- }
-
- bucket->occupied = 1;
- bucket->index = index;
- bucket->next_bucket = END_OF_CHAIN;
+ buckets[t->bucket_info->last_free] = (bucket_t){
+ .occupied = 1, .index=index, .next_bucket=bucket->next_bucket};
+ bucket->next_bucket = t->bucket_info->last_free;
+ }
hshow(t);
}
diff --git a/src/stdlib/text.c b/src/stdlib/text.c
index 2107c1df..80c267ed 100644
--- a/src/stdlib/text.c
+++ b/src/stdlib/text.c
@@ -1,31 +1,58 @@
// This file defines type info and methods for the Text datatype, which uses
// libunistr for Unicode support and implements a datastructure based on a
// hybrid of Raku/MoarVM's space-efficient grapheme cluster representation of
-// strings and Cords (Boehm et al), which have good runtime performance for
-// text constructed by a series of many concatenations.
-//
+// strings, combined with a mostly-balanced tree datastructure based on Cords
+// (Boehm et al), which have good runtime performance for text constructed by a
+// series of many concatenations. In practice, this means Tomo's Text has an
+// extremely compact memory footprint (typically as compact as UTF8 or
+// up to 2x better for some languages), with extremely fast operations
+// including concatenation, random indexing, and taking substrings.
+
// For more information on MoarVM's grapheme cluster strings, see:
// https://docs.raku.org/language/unicode
-// https://github.com/MoarVM/MoarVM/blob/main/docs/strings.asciidoc For more
-// information on Cords, see the paper "Ropes: an Alternative to Strings"
-// (Boehm, Atkinson, Plass 1995):
+// https://github.com/MoarVM/MoarVM/blob/main/docs/strings.asciidoc
+// For more information on Cords, see the paper "Ropes: an Alternative to
+// Strings" (Boehm, Atkinson, Plass 1995):
// https://www.cs.tufts.edu/comp/150FP/archive/hans-boehm/ropes.pdf
-//
-// A note on grapheme clusters: In Unicode, codepoints can be represented using
-// a 32-bit integer. Most codepoints correspond to the intuitive notion of a
-// "letter", which is more formally known as a "grapheme cluster". A grapheme
-// cluster is roughly speaking the amount of text that your cursor moves over
-// when you press the arrow key once. However, some codepoints act as modifiers
-// on other codepoints. For example, U+0301 (COMBINING ACUTE ACCENT) can modify
-// a letter like "e" to form "é". During normalization, this frequently
-// resolves down to a single unicode codepoint, in this case, "é" resolves to
-// the single codepoint U+00E9 (LATIN SMALL LETTER E WITH ACUTE). However, in
-// some cases, multiple codepoints make up a grapheme cluster but *don't*
-// normalize to a single codepoint. For example, LATIN SMALL LETTER E (U+0065)
-// + COMBINING VERTICAL LINE BELOW (U+0329) combine to form an unusual glyph
-// that is not used frequently enough to warrant its own unique codepoint (this
-// is basically what Zalgo text is).
-//
+
+// Tomo's Text datatype represents Unicode text that is fully normalized using
+// normalization form C (NFC). This means that all text created from source code
+// or read in at runtime will respect normalization during comparison and other
+// operations, and the original (potentially non-canonical) representation of
+// text is not preserved. This also means that byte sequences that do not
+// represent valid unicode text cannot be interpreted as the Text datatype. For
+// example, a file with malformed UTF8 sequences cannot be read as Text.
+
+// A note on grapheme clusters: In Unicode, the fundamental unit is the
+// "codepoint", which represents things like letters, symbols, emojis,
+// combiners, and modifiers that alter other codepoints. However, most people
+// have an intuitive notion of what a "letter" is that corresponds to the
+// concept formally known as a grapheme cluster. A grapheme cluster is roughly
+// speaking the amount of text that your cursor moves over when you press the
+// left or right arrow key once. This often corresponds to a single codepoint,
+// but some codepoints act as modifiers on other codepoints. For example, U+0301
+// (COMBINING ACUTE ACCENT) can modify a letter like "e" to form "é". During
+// normalization, this frequently resolves down to a single unicode codepoint,
+// in this case, "é" resolves to the single codepoint U+00E9 (LATIN SMALL LETTER
+// E WITH ACUTE). However, in some cases, multiple codepoints make up a grapheme
+// cluster but *don't* normalize to a single codepoint. For example, LATIN SMALL
+// LETTER E (U+0065) + COMBINING VERTICAL LINE BELOW (U+0329) combine to form an
+// unusual glyph that is not used frequently enough to warrant its own unique
+// codepoint (this is basically what Zalgo text is). Emojis also use the ZERO
+// WIDTH JOINER (U+200D) to add gender, skin tone, or other modifiers to emojis.
+// Tomo takes an opinionated stance that grapheme clusters, not codepoints or
+// bytes, are more useful to people when doing text operations like getting the
+// "length" of a text or accessing the Nth "letter" of a text. If someone sends
+// you a text with WOMAN (U+1F469) + ZERO WIDTH JOINER (U+200D) + ROCKET
+// (U+1F680) followed by THUMBS UP (U+1F44D), it will render on your screen as
+// two things: a female astronaut and a thumbs up, and this is how most people
+// will think about the text. If you wish to operate on the raw codepoints that
+// comprise the message, you are free to do so with the `.utf32_codepoints()`
+// method and `Text.from_codepoints()`, but this is not the default behavior.
+// The behavior for the given example is that `text.length == 2`, `text[1]` is
+// the grapheme cluster representing a female astronaut emoji, and `text[2]` is
+// the grapheme cluster representing the thumbs up emoji.
+
// There are a lot of benefits to storing unicode text with one grapheme
// cluster per index in a densely packed list instead of storing the text as
// variable-width UTF8-encoded bytes. It lets us have one canonical length for
@@ -44,7 +71,7 @@
// things that would be nice if they had their own codepoint so things worked
// out nicely because we're using them right now, and we'll give them a
// negative number so it doesn't overlap with any real codepoints.
-//
+
// Example 1: U+0048, U+00E9 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E
// WITH ACUTE This would be stored as: (int32_t[]){0x48, 0xE9} Example 2:
// U+0048, U+0065, U+0309 AKA: LATIN CAPITAL LETTER H, LATIN SMALL LETTER E,
@@ -52,6 +79,18 @@
// Where -2 is used as a lookup in a list that holds the actual unicode
// codepoints: (ucs4_t[]){0x65, 0x0309}
+// The text datastructure also uses a compact encoding (TEXT_BLOB) to store a
+// per-chunk compressed form of the text when long stretches of text contain
+// 256 or fewer unique grapheme clusters, which lets the text use a single byte
+// for each grapheme cluster along with a lookup table. For typical text
+// written in a variety of non-English natural languages (e.g. Spanish, Arabic,
+// Japanese, Greek, German, Finnish, Basque), the in-memory representation
+// takes up between 50-101% as much space as UTF8 encoding and between 24-39%
+// as much space as UTF32 encoding, but with the advantage of extremely fast
+// random access for indexing or slicing, unlike UTF8. In other words, this
+// representation offers ASCII-like compactness and fast random access for
+// non-English languages.
+
#include <assert.h>
#include <ctype.h>
#include <gc.h>
@@ -68,6 +107,7 @@
#include <unistring/version.h>
#include <uniwidth.h>
+#include "bytes.h"
#include "datatypes.h"
#include "lists.h"
#include "integers.h"
@@ -102,7 +142,6 @@ static int32_t num_synthetic_graphemes = 0;
#define SHORT_ASCII_LENGTH 64
#define SHORT_GRAPHEMES_LENGTH 16
-static Text_t text_from_u32(ucs4_t *codepoints, int64_t num_codepoints, bool normalize);
static Text_t simple_concatenation(Text_t a, Text_t b);
public Text_t EMPTY_TEXT = {
@@ -142,6 +181,9 @@ static const TypeInfo_t GraphemeClusterInfo = {
#endif
public int32_t get_synthetic_grapheme(const ucs4_t *codepoints, int64_t utf32_len)
{
+ if (utf32_len == 1)
+ return (int32_t)*codepoints;
+
ucs4_t length_prefixed[1+utf32_len];
length_prefixed[0] = (ucs4_t)utf32_len;
for (int i = 0; i < utf32_len; i++)
@@ -173,6 +215,7 @@ public int32_t get_synthetic_grapheme(const ucs4_t *codepoints, int64_t utf32_le
uint8_t u8_buf[64];
size_t u8_len = sizeof(u8_buf)/sizeof(u8_buf[0]);
uint8_t *u8 = u32_to_u8(codepoints, (size_t)utf32_len, u8_buf, &u8_len);
+ if (u8 == NULL) fail("Invalid graphemes encountered!");
// For performance reasons, use an arena allocator here to ensure that
// synthetic graphemes store all of their information in a densely packed
@@ -247,6 +290,26 @@ public int Text$print(FILE *stream, Text_t t)
uint8_t buf[8];
size_t len = sizeof(buf);
uint8_t *u8 = u32_to_u8((ucs4_t*)&grapheme, 1, buf, &len);
+ if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme);
+ written += (int)fwrite(u8, sizeof(char), len, stream);
+ if (u8 != buf) free(u8);
+ } else {
+ const uint8_t *u8 = GRAPHEME_UTF8(grapheme);
+ assert(u8);
+ written += (int)fwrite(u8, sizeof(uint8_t), strlen((char*)u8), stream);
+ }
+ }
+ return written;
+ }
+ case TEXT_BLOB: {
+ int written = 0;
+ for (int64_t i = 0; i < t.length; i++) {
+ int32_t grapheme = t.blob.map[t.blob.bytes[i]];
+ if (grapheme >= 0) {
+ uint8_t buf[8];
+ size_t len = sizeof(buf);
+ uint8_t *u8 = u32_to_u8((ucs4_t*)&grapheme, 1, buf, &len);
+ if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme);
written += (int)fwrite(u8, sizeof(char), len, stream);
if (u8 != buf) free(u8);
} else {
@@ -258,8 +321,9 @@ public int Text$print(FILE *stream, Text_t t)
return written;
}
case TEXT_CONCAT: {
- return (Text$print(stream, *t.left)
- + Text$print(stream, *t.right));
+ int written = Text$print(stream, *t.left);
+ written += Text$print(stream, *t.right);
+ return written;
}
default: return 0;
}
@@ -275,18 +339,24 @@ static const int64_t min_len_for_depth[MAX_TEXT_DEPTH] = {
#define IS_BALANCED_TEXT(t) ((t).length >= min_len_for_depth[(t).depth])
-static void insert_balanced(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t to_insert)
+static void insert_balanced_recursive(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t text)
{
+ if (text.tag == TEXT_CONCAT && (!IS_BALANCED_TEXT(text) || text.depth >= MAX_TEXT_DEPTH)) {
+ insert_balanced_recursive(balanced_texts, *text.left);
+ insert_balanced_recursive(balanced_texts, *text.right);
+ return;
+ }
+
int i = 0;
Text_t accumulator = EMPTY_TEXT;
- for (; to_insert.length > min_len_for_depth[i + 1]; i++) {
+ for (; text.length > min_len_for_depth[i + 1]; i++) {
if (balanced_texts[i].length) {
accumulator = simple_concatenation(balanced_texts[i], accumulator);
balanced_texts[i] = EMPTY_TEXT;
}
}
- accumulator = simple_concatenation(accumulator, to_insert);
+ accumulator = simple_concatenation(accumulator, text);
while (accumulator.length >= min_len_for_depth[i]) {
if (balanced_texts[i].length) {
@@ -299,16 +369,6 @@ static void insert_balanced(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t to_ins
balanced_texts[i] = accumulator;
}
-static void insert_balanced_recursive(Text_t balanced_texts[MAX_TEXT_DEPTH], Text_t text)
-{
- if (text.tag == TEXT_CONCAT && (!IS_BALANCED_TEXT(text) || text.depth >= MAX_TEXT_DEPTH)) {
- insert_balanced_recursive(balanced_texts, *text.left);
- insert_balanced_recursive(balanced_texts, *text.right);
- } else {
- insert_balanced(balanced_texts, text);
- }
-}
-
static Text_t rebalanced(Text_t a, Text_t b)
{
Text_t balanced_texts[MAX_TEXT_DEPTH];
@@ -384,15 +444,25 @@ static Text_t concat2_assuming_safe(Text_t a, Text_t b)
if (a.tag == TEXT_GRAPHEMES) {
memcpy(dest, a.graphemes, sizeof(int32_t[a.length]));
dest += a.length;
- } else {
+ } else if (a.tag == TEXT_ASCII) {
for (int64_t i = 0; i < a.length; i++)
*(dest++) = (int32_t)a.ascii[i];
+ } else if (a.tag == TEXT_BLOB) {
+ for (int64_t i = 0; i < a.length; i++)
+ *(dest++) = a.blob.map[a.blob.bytes[i]];
+ } else {
+ errx(1, "Unreachable");
}
if (b.tag == TEXT_GRAPHEMES) {
memcpy(dest, b.graphemes, sizeof(int32_t[b.length]));
- } else {
+ } else if (b.tag == TEXT_ASCII) {
for (int64_t i = 0; i < b.length; i++)
*(dest++) = (int32_t)b.ascii[i];
+ } else if (b.tag == TEXT_BLOB) {
+ for (int64_t i = 0; i < b.length; i++)
+ *(dest++) = b.blob.map[b.blob.bytes[i]];
+ } else {
+ errx(1, "Unreachable");
}
return ret;
}
@@ -455,7 +525,7 @@ static Text_t concat2(Text_t a, Text_t b)
return concat2_assuming_safe(a, b);
}
- Text_t glue = text_from_u32(norm_buf, (int64_t)norm_length, false);
+ Text_t glue = Text$from_codepoints((List_t){.data=norm_buf, .length=(int64_t)norm_length, .stride=sizeof(int32_t)});
if (normalized != norm_buf)
free(normalized);
@@ -590,8 +660,8 @@ public Text_t Text$slice(Text_t text, Int_t first_int, Int_t last_int)
last -= text.left->length;
text = *text.right;
} else {
- return concat2(Text$slice(*text.left, I(first), I(text.length)),
- Text$slice(*text.right, I(1), I(last-text.left->length)));
+ return concat2_assuming_safe(Text$slice(*text.left, I(first), I(text.length)),
+ Text$slice(*text.right, I(1), I(last-text.left->length)));
}
}
@@ -610,6 +680,15 @@ public Text_t Text$slice(Text_t text, Int_t first_int, Int_t last_int)
.graphemes=text.graphemes + (first-1),
};
}
+ case TEXT_BLOB: {
+ Text_t ret = (Text_t){
+ .tag=TEXT_BLOB,
+ .length=last - first + 1,
+ .blob.map=text.blob.map,
+ .blob.bytes=text.blob.bytes + (first-1),
+ };
+ return ret;
+ }
default: errx(1, "Invalid tag");
}
return EMPTY_TEXT;
@@ -648,90 +727,64 @@ public Text_t Text$reversed(Text_t text)
((int32_t*)ret.graphemes)[text.length-1-i] = text.graphemes[i];
return ret;
}
- case TEXT_CONCAT: {
- return concat2(Text$reversed(*text.right), Text$reversed(*text.left));
- }
- default: errx(1, "Invalid tag");
- }
- return EMPTY_TEXT;
-}
-
-public PUREFUNC Text_t Text$cluster(Text_t text, Int_t index_int)
-{
- int64_t index = Int64$from_int(index_int, false);
- if (index == 0) fail("Invalid index: 0");
-
- if (index < 0) index = text.length + index + 1;
-
- if (index > text.length || index < 1)
- fail("Invalid index: ", index_int, " is beyond the length of the text (length = ", (int64_t)text.length, ")");
-
- while (text.tag == TEXT_CONCAT) {
- if (index <= text.left->length)
- text = *text.left;
- else
- text = *text.right;
- }
-
- switch (text.tag) {
- case TEXT_ASCII: {
+ case TEXT_BLOB: {
struct Text_s ret = {
- .tag=TEXT_ASCII,
- .length=1,
- .ascii=GC_MALLOC_ATOMIC(sizeof(char)),
+ .tag=TEXT_BLOB,
+ .length=text.length,
+ .blob.map=text.blob.map,
};
- *(char*)&ret.ascii[0] = text.ascii[index-1];
+ ret.blob.bytes = GC_MALLOC_ATOMIC(sizeof(uint8_t[ret.length]));
+ for (int64_t i = 0; i < text.length; i++)
+ ((uint8_t*)ret.blob.bytes)[text.length-1-i] = text.graphemes[i];
return ret;
}
- case TEXT_GRAPHEMES: {
- struct Text_s ret = {
- .tag=TEXT_GRAPHEMES,
- .length=1,
- .graphemes=GC_MALLOC_ATOMIC(sizeof(int32_t)),
- };
- *(int32_t*)&ret.graphemes[0] = text.graphemes[index-1];
- return ret;
+ case TEXT_CONCAT: {
+ return concat2_assuming_safe(Text$reversed(*text.right), Text$reversed(*text.left));
}
default: errx(1, "Invalid tag");
}
return EMPTY_TEXT;
}
-Text_t text_from_u32(ucs4_t *codepoints, int64_t num_codepoints, bool normalize)
+public PUREFUNC Text_t Text$cluster(Text_t text, Int_t index)
{
- // Normalization is apparently guaranteed to never exceed 3x in the input length
- ucs4_t norm_buf[MIN(256, 3*num_codepoints)];
- if (normalize) {
- size_t norm_length = sizeof(norm_buf)/sizeof(norm_buf[0]);
- ucs4_t *normalized = u32_normalize(UNINORM_NFC, codepoints, (size_t)num_codepoints, norm_buf, &norm_length);
- codepoints = normalized;
- num_codepoints = (int64_t)norm_length;
- }
+ return Text$slice(text, index, index);
+}
- // Intentionally overallocate here: allocate assuming each codepoint is a
- // grapheme cluster. If that's not true, we'll have extra space at the end
- // of the list, but the length will still be calculated correctly.
- int32_t *graphemes = GC_MALLOC_ATOMIC(sizeof(int32_t[num_codepoints]));
- struct Text_s ret = {
- .tag=TEXT_GRAPHEMES,
- .length=0,
- .graphemes=graphemes,
- };
- const ucs4_t *src = codepoints;
- while (src < &codepoints[num_codepoints]) {
- // TODO: use grapheme breaks instead of u32_grapheme_next()?
- const ucs4_t *next = u32_grapheme_next(src, &codepoints[num_codepoints]);
- if (next == &src[1]) {
- graphemes[ret.length] = (int32_t)*src;
- } else {
- // Synthetic grapheme
- graphemes[ret.length] = get_synthetic_grapheme(src, next-src);
+static Text_t Text$from_components(List_t graphemes, Table_t unique_clusters)
+{
+ struct {
+ int32_t map[unique_clusters.entries.length];
+ uint8_t bytes[graphemes.length];
+ } *blob;
+ // If blob optimization will save at least 200 bytes:
+ if (unique_clusters.entries.length <= 256 && sizeof(*blob) + 200 < sizeof(int32_t[graphemes.length])) {
+ Text_t ret = {
+ .tag=TEXT_BLOB,
+ .length=graphemes.length,
+ .depth=0,
+ };
+ blob = GC_MALLOC_ATOMIC(sizeof(*blob));
+ for (int64_t i = 0; i < unique_clusters.entries.length; i++) {
+ struct { int32_t g; uint8_t b; } *entry = unique_clusters.entries.data + i*unique_clusters.entries.stride;
+ blob->map[entry->b] = entry->g;
}
- ++ret.length;
- src = next;
+ for (int64_t i = 0; i < graphemes.length; i++) {
+ int32_t g = *(int32_t*)(graphemes.data + i*graphemes.stride);
+ uint8_t *byte = Table$get(unique_clusters, &g, Table$info(&Int32$info, &Byte$info));
+ assert(byte);
+ blob->bytes[i] = *byte;
+ }
+ ret.blob.map = &blob->map[0];
+ ret.blob.bytes = &blob->bytes[0];
+ return ret;
+ } else {
+ return (Text_t){
+ .tag=TEXT_GRAPHEMES,
+ .length=graphemes.length,
+ .graphemes=graphemes.data,
+ };
}
- if (normalize && codepoints != norm_buf) free(codepoints);
- return ret;
}
public OptionalText_t Text$from_strn(const char *str, size_t len)
@@ -748,18 +801,37 @@ public OptionalText_t Text$from_strn(const char *str, size_t len)
.length=ascii_span,
.ascii=copy,
};
- } else {
- if (u8_check((uint8_t*)str, len) != NULL)
- return NONE_TEXT;
-
- ucs4_t buf[128];
- size_t length = sizeof(buf)/sizeof(buf[0]);
+ }
+ if (u8_check((uint8_t*)str, len) != NULL)
+ return NONE_TEXT;
- ucs4_t *codepoints = u8_to_u32((uint8_t*)str, (size_t)ascii_span + strlen(str + ascii_span), buf, &length);
- Text_t ret = text_from_u32(codepoints, (int64_t)length, true);
- if (codepoints != buf) free(codepoints);
- return ret;
+ List_t graphemes = {};
+ Table_t unique_clusters = {};
+ const uint8_t *pos = (const uint8_t*)str;
+ const uint8_t *end = (const uint8_t*)&str[len];
+ // Iterate over grapheme clusters
+ for (const uint8_t *next; (next=u8_grapheme_next(pos, end)); pos = next) {
+ uint32_t buf[256];
+ size_t u32_len = sizeof(buf)/sizeof(buf[0]);
+ uint32_t *u32s = u8_to_u32(pos, (size_t)(next-pos), buf, &u32_len);
+
+ uint32_t buf2[256];
+ size_t u32_normlen = sizeof(buf2)/sizeof(buf2[0]);
+ uint32_t *u32s_normalized = u32_normalize(UNINORM_NFC, u32s, u32_len, buf2, &u32_normlen);
+
+ int32_t g = get_synthetic_grapheme(u32s_normalized, (int64_t)u32_normlen);
+ List$insert(&graphemes, &g, I(0), sizeof(int32_t));
+ Table$get_or_setdefault(&unique_clusters, int32_t, uint8_t, g, (uint8_t)unique_clusters.entries.length, Table$info(&Int32$info, &Byte$info));
+
+ if (u32s != buf) free(u32s);
+ if (u32s_normalized != buf2) free(u32s_normalized);
+
+ if (unique_clusters.entries.length >= 256) {
+ return concat2_assuming_safe(Text$from_components(graphemes, unique_clusters), Text$from_strn(next, (size_t)(end-next)));
+ }
}
+
+ return Text$from_components(graphemes, unique_clusters);
}
public OptionalText_t Text$from_str(const char *str)
@@ -788,6 +860,7 @@ static void u8_buf_append(Text_t text, char **buf, int64_t *capacity, int64_t *i
uint8_t u8_buf[64];
size_t u8_len = sizeof(u8_buf);
uint8_t *u8 = u32_to_u8((ucs4_t*)&graphemes[g], 1, u8_buf, &u8_len);
+ if (u8 == NULL) fail("Invalid grapheme encountered: ", graphemes[g]);
if (*i + (int64_t)u8_len > (int64_t)*capacity) {
*capacity = *i + (int64_t)u8_len + 1;
@@ -811,6 +884,37 @@ static void u8_buf_append(Text_t text, char **buf, int64_t *capacity, int64_t *i
}
break;
}
+ case TEXT_BLOB: {
+ for (int64_t g = 0; g < text.length; g++) {
+ int32_t grapheme = text.blob.map[text.blob.bytes[g]];
+ if (grapheme >= 0) {
+ uint8_t u8_buf[64];
+ size_t u8_len = sizeof(u8_buf);
+ uint8_t *u8 = u32_to_u8((ucs4_t*)&grapheme, 1, u8_buf, &u8_len);
+ if (u8 == NULL) fail("Invalid grapheme encountered: ", grapheme);
+
+ if (*i + (int64_t)u8_len > (int64_t)*capacity) {
+ *capacity = *i + (int64_t)u8_len + 1;
+ *buf = GC_REALLOC(*buf, (size_t)*capacity);
+ }
+
+ memcpy(*buf + *i, u8, u8_len);
+ *i += (int64_t)u8_len;
+ if (u8 != u8_buf) free(u8);
+ } else {
+ const uint8_t *u8 = GRAPHEME_UTF8(grapheme);
+ size_t u8_len = u8_strlen(u8);
+ if (*i + (int64_t)u8_len > (int64_t)*capacity) {
+ *capacity = *i + (int64_t)u8_len + 1;
+ *buf = GC_REALLOC(*buf, (size_t)*capacity);
+ }
+
+ memcpy(*buf + *i, u8, u8_len);
+ *i += (int64_t)u8_len;
+ }
+ }
+ break;
+ }
case TEXT_CONCAT: {
u8_buf_append(*text.left, buf, capacity, i);
u8_buf_append(*text.right, buf, capacity, i);
@@ -867,6 +971,15 @@ PUREFUNC public uint64_t Text$hash(const void *obj, const TypeInfo_t *info)
int32_t last = text.length & 0x1 ? graphemes[text.length-1] : 0; // Odd number of graphemes
return siphashfinish_last_part(&sh, (uint64_t)last);
}
+ case TEXT_BLOB: {
+ for (int64_t i = 0; i + 1 < text.length; i += 2) {
+ tmp.chunks[0] = text.blob.map[text.blob.bytes[i]];
+ tmp.chunks[1] = text.blob.map[text.blob.bytes[i+1]];
+ siphashadd64bits(&sh, tmp.whole);
+ }
+ int32_t last = text.length & 0x1 ? text.blob.map[text.blob.bytes[text.length-1]] : 0; // Odd number of graphemes
+ return siphashfinish_last_part(&sh, (uint64_t)last);
+ }
case TEXT_CONCAT: {
TextIter_t state = NEW_TEXT_ITER_STATE(text);
for (int64_t i = 0; i + 1 < text.length; i += 2) {
@@ -928,6 +1041,7 @@ public int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index)
switch (text.tag) {
case TEXT_ASCII: return (int32_t)text.ascii[index - offset];
case TEXT_GRAPHEMES: return text.graphemes[index - offset];
+ case TEXT_BLOB: return text.blob.map[text.blob.bytes[index - offset]];
default: errx(1, "Invalid text");
}
return 0;
@@ -1286,11 +1400,9 @@ public Text_t Text$upper(Text_t text, Text_t language)
if (text.length == 0) return text;
List_t codepoints = Text$utf32_codepoints(text);
const char *uc_language = Text$as_c_string(language);
- ucs4_t buf[128];
- size_t out_len = sizeof(buf)/sizeof(buf[0]);
- ucs4_t *upper = u32_toupper(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len);
- Text_t ret = text_from_u32(upper, (int64_t)out_len, false);
- if (upper != buf) free(upper);
+ size_t out_len = 0;
+ ucs4_t *upper = u32_toupper(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len);
+ Text_t ret = Text$from_codepoints((List_t){.data=upper, .length=(int64_t)out_len, .stride=sizeof(int32_t)});
return ret;
}
@@ -1299,11 +1411,9 @@ public Text_t Text$lower(Text_t text, Text_t language)
if (text.length == 0) return text;
List_t codepoints = Text$utf32_codepoints(text);
const char *uc_language = Text$as_c_string(language);
- ucs4_t buf[128];
- size_t out_len = sizeof(buf)/sizeof(buf[0]);
- ucs4_t *lower = u32_tolower(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len);
- Text_t ret = text_from_u32(lower, (int64_t)out_len, false);
- if (lower != buf) free(lower);
+ size_t out_len = 0;
+ ucs4_t *lower = u32_tolower(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len);
+ Text_t ret = Text$from_codepoints((List_t){.data=lower, .length=(int64_t)out_len, .stride=sizeof(int32_t)});
return ret;
}
@@ -1312,11 +1422,9 @@ public Text_t Text$title(Text_t text, Text_t language)
if (text.length == 0) return text;
List_t codepoints = Text$utf32_codepoints(text);
const char *uc_language = Text$as_c_string(language);
- ucs4_t buf[128];
- size_t out_len = sizeof(buf)/sizeof(buf[0]);
- ucs4_t *title = u32_totitle(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, buf, &out_len);
- Text_t ret = text_from_u32(title, (int64_t)out_len, false);
- if (title != buf) free(title);
+ size_t out_len = 0;
+ ucs4_t *title = u32_totitle(codepoints.data, (size_t)codepoints.length, uc_language, UNINORM_NFC, NULL, &out_len);
+ Text_t ret = Text$from_codepoints((List_t){.data=title, .length=(int64_t)out_len, .stride=sizeof(int32_t)});
return ret;
}
@@ -1332,12 +1440,20 @@ public Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark)
ret = concat2_assuming_safe(ret, quotation_mark);
int32_t quote_char = Text$get_grapheme(quotation_mark, 0);
-#define add_escaped(str) ({ if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m")); \
+#define flush_unquoted() ({ \
+ if (unquoted_span > 0) { \
+ ret = concat2_assuming_safe(ret, Text$slice(text, I(i-unquoted_span+1), I(i))); \
+ unquoted_span = 0; \
+ } })
+#define add_escaped(str) ({ \
+ flush_unquoted(); \
+ if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m")); \
ret = concat2_assuming_safe(ret, Text("\\" str)); \
if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m")); })
TextIter_t state = NEW_TEXT_ITER_STATE(text);
- // TODO: optimize for spans of non-escaped text
- for (int64_t i = 0; i < text.length; i++) {
+ int64_t unquoted_span = 0;
+ int64_t i = 0;
+ for (i = 0; i < text.length; i++) {
int32_t g = Text$get_grapheme_fast(&state, i);
switch (g) {
case '\a': add_escaped("a"); break;
@@ -1358,6 +1474,7 @@ public Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark)
}
case '\x00' ... '\x06': case '\x0E' ... '\x1A':
case '\x1C' ... '\x1F': case '\x7F' ... '\x7F': {
+ flush_unquoted();
if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m"));
ret = concat2_assuming_safe(ret, Text("\\x"));
char tmp[3] = {
@@ -1372,15 +1489,21 @@ public Text_t Text$quoted(Text_t text, bool colorize, Text_t quotation_mark)
}
default: {
if (g == quote_char) {
+ flush_unquoted();
+ if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[34;1m"));
+ ret = concat2_assuming_safe(ret, Text("\\"));
ret = concat2_assuming_safe(ret, quotation_mark);
+ if (colorize) ret = concat2_assuming_safe(ret, Text("\x1b[0;35m"));
} else {
- ret = concat2_assuming_safe(ret, Text$slice(text, I(i+1), I(i+1)));
+ unquoted_span += 1;
}
break;
}
}
}
+ flush_unquoted();
#undef add_escaped
+#undef flush_unquoted
ret = concat2_assuming_safe(ret, quotation_mark);
if (colorize)
@@ -1477,7 +1600,7 @@ public List_t Text$utf32_codepoints(Text_t text)
public List_t Text$utf8_bytes(Text_t text)
{
const char *str = Text$as_c_string(text);
- return (List_t){.length=strlen(str), .stride=1, .atomic=1, .data=(void*)str};
+ return (List_t){.length=(int64_t)strlen(str), .stride=1, .atomic=1, .data=(void*)str};
}
static INLINE const char *codepoint_name(ucs4_t c)
@@ -1513,10 +1636,38 @@ public List_t Text$codepoint_names(Text_t text)
public Text_t Text$from_codepoints(List_t codepoints)
{
- if (codepoints.stride != sizeof(int32_t))
- List$compact(&codepoints, sizeof(int32_t));
-
- return text_from_u32(codepoints.data, codepoints.length, true);
+ if (codepoints.stride != sizeof(uint32_t))
+ List$compact(&codepoints, sizeof(uint32_t));
+
+ List_t graphemes = {};
+ Table_t unique_clusters = {};
+ const uint32_t *pos = (const uint32_t*)codepoints.data;
+ const uint32_t *end = (const uint32_t*)&pos[codepoints.length];
+ // Iterate over grapheme clusters
+ for (const uint32_t *next; (next=u32_grapheme_next(pos, end)); pos = next) {
+ // Buffer for normalized cluster:
+ uint32_t buf[256];
+ size_t u32_normlen = sizeof(buf)/sizeof(buf[0]);
+ uint32_t *u32s_normalized = u32_normalize(UNINORM_NFC, pos, (size_t)(next-pos), buf, &u32_normlen);
+
+ int32_t g = get_synthetic_grapheme(u32s_normalized, (int64_t)u32_normlen);
+ List$insert(&graphemes, &g, I(0), sizeof(int32_t));
+ Table$get_or_setdefault(
+ &unique_clusters, int32_t, uint8_t, g, (uint8_t)unique_clusters.entries.length,
+ Table$info(&Int32$info, &Byte$info));
+
+ if (u32s_normalized != buf) free(u32s_normalized);
+
+ if (unique_clusters.entries.length == 256) {
+ List_t remaining_codepoints = {
+ .length=(int64_t)(end-next),
+ .data=(void*)next,
+ .stride=sizeof(int32_t),
+ };
+ return concat2_assuming_safe(Text$from_components(graphemes, unique_clusters), Text$from_codepoints(remaining_codepoints));
+ }
+ }
+ return Text$from_components(graphemes, unique_clusters);
}
public OptionalText_t Text$from_codepoint_names(List_t codepoint_names)
@@ -1605,6 +1756,38 @@ PUREFUNC public bool Text$is_none(const void *t, const TypeInfo_t *info)
return ((Text_t*)t)->length < 0;
}
+public Int_t Text$memory_size(Text_t text)
+{
+ switch (text.tag) {
+ case TEXT_ASCII:
+ return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)sizeof(char[text.length]));
+ case TEXT_GRAPHEMES:
+ return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)sizeof(int32_t[text.length]));
+ case TEXT_BLOB:
+ return Int$from_int64((int64_t)sizeof(Text_t) + (int64_t)((void*)text.blob.bytes - (void*)text.blob.map) + (int64_t)sizeof(uint8_t[text.length]));
+ case TEXT_CONCAT:
+ return Int$plus(
+ Int$from_int64((int64_t)sizeof(Text_t)),
+ Int$plus(Text$memory_size(*text.left), Text$memory_size(*text.right)));
+ default: errx(1, "Invalid text tag: ", text.tag);
+ }
+}
+
+public Text_t Text$layout(Text_t text)
+{
+ switch (text.tag) {
+ case TEXT_ASCII:
+ return Texts(Text("ASCII("), Int64$as_text((int64_t[1]){text.length}, false, NULL), Text(")"));
+ case TEXT_GRAPHEMES:
+ return Texts(Text("Graphemes("), Int64$as_text((int64_t[1]){text.length}, false, NULL), Text(")"));
+ case TEXT_BLOB:
+ return Texts(Text("Blob("), Int64$as_text((int64_t[1]){text.length}, false, NULL), Text(")"));
+ case TEXT_CONCAT:
+ return Texts(Text("Concat("), Text$layout(*text.left), Text(", "), Text$layout(*text.right), Text(")"));
+ default: errx(1, "Invalid text tag: ", text.tag);
+ }
+}
+
public void Text$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *info)
{
(void)info;
@@ -1617,8 +1800,10 @@ public void Text$serialize(const void *obj, FILE *out, Table_t *pointers, const
public void Text$deserialize(FILE *in, void *out, List_t *pointers, const TypeInfo_t *info)
{
(void)info;
- int64_t len = -1;
+ int64_t len = 0;
Int64$deserialize(in, &len, pointers, &Int64$info);
+ if (len < 0)
+ fail("Cannot deserialize text with a negative length!");
char *buf = GC_MALLOC_ATOMIC((size_t)len+1);
if (fread(buf, sizeof(char), (size_t)len, in) != (size_t)len)
fail("Not enough data in stream to deserialize");
diff --git a/src/stdlib/text.h b/src/stdlib/text.h
index 47ede6f1..fc336612 100644
--- a/src/stdlib/text.h
+++ b/src/stdlib/text.h
@@ -78,6 +78,8 @@ Text_t Text$right_pad(Text_t text, Int_t width, Text_t padding, Text_t language)
Text_t Text$middle_pad(Text_t text, Int_t width, Text_t padding, Text_t language);
int32_t Text$get_grapheme_fast(TextIter_t *state, int64_t index);
uint32_t Text$get_main_grapheme_fast(TextIter_t *state, int64_t index);
+Int_t Text$memory_size(Text_t text);
+Text_t Text$layout(Text_t text);
void Text$serialize(const void *obj, FILE *out, Table_t *, const TypeInfo_t *);
void Text$deserialize(FILE *in, void *out, List_t *, const TypeInfo_t *);
diff --git a/src/tomo.c b/src/tomo.c
index 02891bef..53d07163 100644
--- a/src/tomo.c
+++ b/src/tomo.c
@@ -647,13 +647,67 @@ void build_file_dependency_graph(Path_t path, Table_t *to_compile, Table_t *to_l
asm_path = Path$concat(Path$parent(path), asm_path);
Text_t linker_text = Path$as_text(&asm_path, NULL, &Path$info);
Table$set(to_link, &linker_text, NULL, Table$info(&Text$info, &Void$info));
+ if (is_stale(build_file(path, ".o"), asm_path, false)) {
+ staleness.o = true;
+ Table$set(to_compile, &path, &staleness, Table$info(&Path$info, &Byte$info));
+ }
+ break;
+ }
+ case USE_HEADER: case USE_C_CODE: {
+ Path_t dep_path = Path$from_str(use->path);
+ if (is_stale(build_file(path, ".o"), dep_path, false)) {
+ staleness.o = true;
+ Table$set(to_compile, &path, &staleness, Table$info(&Path$info, &Byte$info));
+ }
break;
}
- default: case USE_HEADER: break;
+ default: break;
}
}
}
+time_t latest_included_modification_time(Path_t path)
+{
+ static Table_t c_modification_times = {};
+ const TypeInfo_t time_info = {.size=sizeof(time_t), .align=alignof(time_t), .tag=OpaqueInfo};
+ time_t *cached_latest = Table$get(c_modification_times, &path, Table$info(&Path$info, &time_info));
+ if (cached_latest) return *cached_latest;
+
+ struct stat s;
+ time_t latest = 0;
+ if (stat(Path$as_c_string(path), &s) == 0)
+ latest = s.st_mtime;
+ Table$set(&c_modification_times, &path, &latest, Table$info(&Path$info, &time_info));
+
+ OptionalClosure_t by_line = Path$by_line(path);
+ if (by_line.fn == NULL) return 0;
+ OptionalText_t (*next_line)(void*) = by_line.fn;
+ Path_t parent = Path$parent(path);
+ bool allow_dot_include = Path$has_extension(path, Text("s")) || Path$has_extension(path, Text("S"));
+ for (Text_t line; (line=next_line(by_line.userdata)).length >= 0; ) {
+ line = Text$trim(line, Text(" \t"), true, false);
+ if (!Text$starts_with(line, Text("#include")) && !(allow_dot_include && Text$starts_with(line, Text(".include"))))
+ continue;
+
+ // Check for `"` after `#include` or `.include` and some spaces:
+ if (!Text$starts_with(Text$trim(Text$from(line, I(9)), Text(" \t"), true, false), Text("\"")))
+ continue;
+
+ List_t chunks = Text$split(line, Text("\""));
+ if (chunks.length < 3) // Should be `#include "foo" ...` -> ["#include ", "foo", "..."]
+ continue;
+
+ Text_t included = *(Text_t*)(chunks.data + 1*chunks.stride);
+ Path_t included_path = Path$resolved(Path$from_text(included), parent);
+ time_t included_time = latest_included_modification_time(included_path);
+ if (included_time > latest) {
+ latest = included_time;
+ Table$set(&c_modification_times, &path, &latest, Table$info(&Path$info, &time_info));
+ }
+ }
+ return latest;
+}
+
bool is_stale(Path_t path, Path_t relative_to, bool ignore_missing)
{
struct stat target_stat;
@@ -668,6 +722,12 @@ bool is_stale(Path_t path, Path_t relative_to, bool ignore_missing)
return true;
#endif
+ if (Path$has_extension(relative_to, Text("c")) || Path$has_extension(relative_to, Text("h"))
+ || Path$has_extension(relative_to, Text("s")) || Path$has_extension(relative_to, Text("S"))) {
+ time_t mtime = latest_included_modification_time(relative_to);
+ return target_stat.st_mtime < mtime;
+ }
+
struct stat relative_to_stat;
if (stat(Path$as_c_string(relative_to), &relative_to_stat) != 0) {
if (ignore_missing) return false;
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-01 06:17:43 +0000