Merge branch 'master' into xml

7 files changed, 270 insertions, 101 deletions

diff --git a/core/container/intrusive/list/intrusive_list.odin b/core/container/intrusive/list/intrusive_list.odin
new file mode 100644
index 000000000..88e21edc5
--- /dev/null
+++ b/core/container/intrusive/list/intrusive_list.odin
@@ -0,0 +1,173 @@
+package container_intrusive_list
+
+import "core:intrinsics"
+
+// An intrusive doubly-linked list
+//
+// As this is an intrusive container, a `Node` must be embedded in your own
+// structure which is conventionally called a "link". The use of `push_front`
+// and `push_back` take the address of this node. Retrieving the data
+// associated with the node requires finding the relative offset of the node
+// of the parent structure. The parent type and field name are given to
+// `iterator_*` procedures, or to the built-in `container_of` procedure.
+//
+// This data structure is two-pointers in size:
+// 	8 bytes on 32-bit platforms and 16 bytes on 64-bit platforms
+List :: struct {
+	head: ^Node,
+	tail: ^Node,
+}
+
+
+Node :: struct {
+	next, prev: ^Node,
+}
+
+push_front :: proc(list: ^List, node: ^Node) {
+	if list.head != nil {
+		list.head.prev = node
+		node.prev, node.next = nil, list.head
+		list.head = node
+	} else {
+		list.head, list.tail = node, node
+		node.prev, node.next = nil, nil
+	}
+}
+
+push_back :: proc(list: ^List, node: ^Node) {
+	if list.tail != nil {
+		list.tail.next = node
+		node.prev, node.next = list.tail, nil
+		list.tail = node
+	} else {
+		list.head, list.tail = node, node
+		node.prev, node.next = nil, nil
+	}
+}
+
+remove :: proc(list: ^List, node: ^Node) {
+	if node != nil {
+		if node.next != nil {
+			node.next.prev = node.prev
+		}
+		if node.prev != nil {
+			node.prev.next = node.next
+		}
+		if list.head == node {
+			list.head = node.next
+		}
+		if list.tail == node {
+			list.tail = node.prev
+		}
+	}
+}
+
+remove_by_proc :: proc(list: ^List, to_erase: proc(^Node) -> bool) {
+	for node := list.head; node != nil; {
+		next := node.next
+		if to_erase(node) {
+			if node.next != nil {
+				node.next.prev = node.prev
+			}
+			if node.prev != nil {
+				node.prev.next = node.next
+			}
+			if list.head == node {
+				list.head = node.next
+			}
+			if list.tail == node {
+				list.tail = node.prev
+			}
+		}
+		node = next
+	}
+}
+
+
+is_empty :: proc(list: ^List) -> bool {
+	return list.head == nil
+}
+
+pop_front :: proc(list: ^List) -> ^Node {
+	link := list.head
+	if link == nil {
+		return nil
+	}
+	if link.next != nil {
+		link.next.prev = link.prev
+	}
+	if link.prev != nil {
+		link.prev.next = link.next
+	}
+	if link == list.head {
+		list.head = link.next
+	}
+	if link == list.tail {
+		list.tail = link.prev
+	}
+	return link
+
+}
+pop_back :: proc(list: ^List) -> ^Node {
+	link := list.tail
+	if link == nil {
+		return nil
+	}
+	if link.next != nil {
+		link.next.prev = link.prev
+	}
+	if link.prev != nil {
+		link.prev.next = link.next
+	}
+	if link == list.head {
+		list.head = link.next
+	}
+	if link == list.tail {
+		list.tail = link.prev
+	}
+	return link
+}
+
+
+Iterator :: struct($T: typeid) {
+	curr:   ^Node,
+	offset: uintptr,
+}
+
+iterator_head :: proc(list: List, $T: typeid, $field_name: string) -> Iterator(T)
+	where intrinsics.type_has_field(T, field_name),
+	      intrinsics.type_field_type(T, field_name) == Node {
+	return {list.head, offset_of_by_string(T, field_name)}
+}
+
+iterator_tail :: proc(list: List, $T: typeid, $field_name: string) -> Iterator(T)
+	where intrinsics.type_has_field(T, field_name),
+	      intrinsics.type_field_type(T, field_name) == Node {
+	return {list.tail, offset_of_by_string(T, field_name)}
+}
+
+iterator_from_node :: proc(node: ^Node, $T: typeid, $field_name: string) -> Iterator(T)
+	where intrinsics.type_has_field(T, field_name),
+	      intrinsics.type_field_type(T, field_name) == Node {
+	return {node, offset_of_by_string(T, field_name)}
+}
+
+iterate_next :: proc(it: ^Iterator($T)) -> (ptr: ^T, ok: bool) {
+	node := it.curr
+	if node == nil {
+		return nil, false
+	}
+	it.curr = node.next
+
+	return (^T)(uintptr(node) - it.offset), true
+}
+
+iterate_prev :: proc(it: ^Iterator($T)) -> (ptr: ^T, ok: bool) {
+	node := it.curr
+	if node == nil {
+		return nil, false
+	}
+	it.curr = node.prev
+
+	return (^T)(uintptr(node) - it.offset), true
+}
\ No newline at end of file
diff --git a/core/intrinsics/intrinsics.odin b/core/intrinsics/intrinsics.odin
index c132d4095..beb6f3f31 100644
--- a/core/intrinsics/intrinsics.odin
+++ b/core/intrinsics/intrinsics.odin
@@ -41,6 +41,10 @@ mem_copy_non_overlapping :: proc(dst, src: rawptr, len: int) ---
 mem_zero                 :: proc(ptr: rawptr, len: int) ---
 mem_zero_volatile        :: proc(ptr: rawptr, len: int) ---
 
+// prefer [^]T operations if possible
+ptr_offset :: proc(ptr: ^$T, offset: int) -> ^T ---
+ptr_sub    :: proc(a, b: ^$T) -> int ---
+
 unaligned_load           :: proc(src: ^$T) -> T ---
 unaligned_store          :: proc(dst: ^$T, val: T) -> T ---
 
@@ -82,6 +86,7 @@ atomic_store_explicit :: proc(dst: ^$T, val: T, order: Atomic_Memory_Order) ---
 atomic_load           :: proc(dst: ^$T) -> T ---
 atomic_load_explicit  :: proc(dst: ^$T, order: Atomic_Memory_Order) -> T ---
 
+// fetch then operator
 atomic_add               :: proc(dst; ^$T, val: T) -> T ---
 atomic_add_explicit      :: proc(dst; ^$T, val: T, order: Atomic_Memory_Order) -> T ---
 atomic_sub               :: proc(dst; ^$T, val: T) -> T ---
@@ -119,19 +124,20 @@ type_is_string     :: proc($T: typeid) -> bool ---
 type_is_typeid     :: proc($T: typeid) -> bool ---
 type_is_any        :: proc($T: typeid) -> bool ---
 
-type_is_endian_platform :: proc($T: typeid) -> bool ---
-type_is_endian_little   :: proc($T: typeid) -> bool ---
-type_is_endian_big      :: proc($T: typeid) -> bool ---
-type_is_unsigned        :: proc($T: typeid) -> bool ---
-type_is_numeric         :: proc($T: typeid) -> bool ---
-type_is_ordered         :: proc($T: typeid) -> bool ---
-type_is_ordered_numeric :: proc($T: typeid) -> bool ---
-type_is_indexable       :: proc($T: typeid) -> bool ---
-type_is_sliceable       :: proc($T: typeid) -> bool ---
-type_is_comparable      :: proc($T: typeid) -> bool ---
-type_is_simple_compare  :: proc($T: typeid) -> bool --- // easily compared using memcmp (== and !=)
-type_is_dereferenceable :: proc($T: typeid) -> bool ---
-type_is_valid_map_key   :: proc($T: typeid) -> bool ---
+type_is_endian_platform       :: proc($T: typeid) -> bool ---
+type_is_endian_little         :: proc($T: typeid) -> bool ---
+type_is_endian_big            :: proc($T: typeid) -> bool ---
+type_is_unsigned              :: proc($T: typeid) -> bool ---
+type_is_numeric               :: proc($T: typeid) -> bool ---
+type_is_ordered               :: proc($T: typeid) -> bool ---
+type_is_ordered_numeric       :: proc($T: typeid) -> bool ---
+type_is_indexable             :: proc($T: typeid) -> bool ---
+type_is_sliceable             :: proc($T: typeid) -> bool ---
+type_is_comparable            :: proc($T: typeid) -> bool ---
+type_is_simple_compare        :: proc($T: typeid) -> bool --- // easily compared using memcmp (== and !=)
+type_is_dereferenceable       :: proc($T: typeid) -> bool ---
+type_is_valid_map_key         :: proc($T: typeid) -> bool ---
+type_is_valid_matrix_elements :: proc($T: typeid) -> bool ---
 
 type_is_named            :: proc($T: typeid) -> bool ---
 type_is_pointer          :: proc($T: typeid) -> bool ---
@@ -146,6 +152,7 @@ type_is_enum             :: proc($T: typeid) -> bool ---
 type_is_proc             :: proc($T: typeid) -> bool ---
 type_is_bit_set          :: proc($T: typeid) -> bool ---
 type_is_simd_vector      :: proc($T: typeid) -> bool ---
+type_is_matrix           :: proc($T: typeid) -> bool ---
 
 type_has_nil :: proc($T: typeid) -> bool ---
 
@@ -161,20 +168,41 @@ type_proc_return_count    :: proc($T: typeid) -> int where type_is_proc(T) ---
 type_proc_parameter_type  :: proc($T: typeid, index: int) -> typeid where type_is_proc(T) ---
 type_proc_return_type     :: proc($T: typeid, index: int) -> typeid where type_is_proc(T) ---
 
+type_struct_field_count :: proc($T: typeid) -> int where type_is_struct(T) ---
+
 type_polymorphic_record_parameter_count :: proc($T: typeid) -> typeid ---
 type_polymorphic_record_parameter_value :: proc($T: typeid, index: int) -> $V ---
 
+type_is_specialized_polymorphic_record   :: proc($T: typeid) -> bool ---
+type_is_unspecialized_polymorphic_record :: proc($T: typeid) -> bool ---
+
+type_is_subtype_of :: proc($T, $U: typeid) -> bool ---
 
 type_field_index_of :: proc($T: typeid, $name: string) -> uintptr ---
 
 type_equal_proc  :: proc($T: typeid) -> (equal:  proc "contextless" (rawptr, rawptr) -> bool)                 where type_is_comparable(T) ---
 type_hasher_proc :: proc($T: typeid) -> (hasher: proc "contextless" (data: rawptr, seed: uintptr) -> uintptr) where type_is_comparable(T) ---
 
+constant_utf16_cstring :: proc($literal: string) -> [^]u16 ---
 
 // WASM targets only
 wasm_memory_grow :: proc(index, delta: uintptr) -> int ---
 wasm_memory_size :: proc(index: uintptr)        -> int ---
 
+
+// Darwin targets only
+objc_object   :: struct{}
+objc_selector :: struct{}
+objc_class    :: struct{}
+objc_id    :: ^objc_object
+objc_SEL   :: ^objc_selector
+objc_Class :: ^objc_class
+
+objc_find_selector     :: proc($name: string) -> objc_SEL   ---
+objc_register_selector :: proc($name: string) -> objc_SEL   ---
+objc_find_class        :: proc($name: string) -> objc_Class ---
+objc_register_class    :: proc($name: string) -> objc_Class ---
+
 // Internal compiler use only
 
 __entry_point :: proc() ---
\ No newline at end of file
diff --git a/core/sync/primitives_atomic.odin b/core/sync/primitives_atomic.odin
index 11fff4e60..22771443d 100644
--- a/core/sync/primitives_atomic.odin
+++ b/core/sync/primitives_atomic.odin
@@ -400,30 +400,28 @@ atomic_cond_broadcast :: proc(c: ^Atomic_Cond) {
 //
 // An Atomic_Sema must not be copied after first use
 Atomic_Sema :: struct {
-	mutex: Atomic_Mutex,
-	cond:  Atomic_Cond,
-	count: int,
+	count: Futex,
 }
 
 atomic_sema_post :: proc(s: ^Atomic_Sema, count := 1) {
-	atomic_mutex_lock(&s.mutex)
-	defer atomic_mutex_unlock(&s.mutex)
-
-	s.count += count
-	atomic_cond_signal(&s.cond)
+	atomic_add_explicit(&s.count, Futex(count), .Release)
+	if count == 1 {
+		futex_signal(&s.count)
+	} else {
+		futex_broadcast(&s.count)
+	}
 }
 
 atomic_sema_wait :: proc(s: ^Atomic_Sema) {
-	atomic_mutex_lock(&s.mutex)
-	defer atomic_mutex_unlock(&s.mutex)
-
-	for s.count == 0 {
-		atomic_cond_wait(&s.cond, &s.mutex)
-	}
-
-	s.count -= 1
-	if s.count > 0 {
-		atomic_cond_signal(&s.cond)
+	for {
+		original_count := atomic_load_explicit(&s.count, .Relaxed)
+		for original_count == 0 {
+			futex_wait(&s.count, u32(original_count))
+			original_count = s.count
+		}
+		if original_count == atomic_compare_exchange_strong_explicit(&s.count, original_count, original_count-1, .Acquire, .Acquire) {
+			return
+		}
 	}
 }
 
@@ -431,25 +429,22 @@ atomic_sema_wait_with_timeout :: proc(s: ^Atomic_Sema, duration: time.Duration)
 	if duration <= 0 {
 		return false
 	}
-	atomic_mutex_lock(&s.mutex)
-	defer atomic_mutex_unlock(&s.mutex)
-	
-	start := time.tick_now()
+	for {
 
-	for s.count == 0 {
-		remaining := duration - time.tick_since(start)
-		if remaining < 0 {
-			return false
+		original_count := atomic_load_explicit(&s.count, .Relaxed)
+		for start := time.tick_now(); original_count == 0; /**/ {
+			remaining := duration - time.tick_since(start)
+			if remaining < 0 {
+				return false
+			}
+
+			if !futex_wait_with_timeout(&s.count, u32(original_count), remaining) {
+				return false
+			}
+			original_count = s.count
 		}
-		
-		if !atomic_cond_wait_with_timeout(&s.cond, &s.mutex, remaining) {
-			return false
+		if original_count == atomic_compare_exchange_strong_explicit(&s.count, original_count, original_count-1, .Acquire, .Acquire) {
+			return true
 		}
 	}
-
-	s.count -= 1
-	if s.count > 0 {
-		atomic_cond_signal(&s.cond)
-	}
-	return true
 }
diff --git a/core/sync/sema_internal.odin b/core/sync/sema_internal.odin
index e4a3c0bfc..5e2203c34 100644
--- a/core/sync/sema_internal.odin
+++ b/core/sync/sema_internal.odin
@@ -6,53 +6,19 @@ import "core:time"
 
 when #config(ODIN_SYNC_SEMA_USE_FUTEX, true) {
 	_Sema :: struct {
-		count: Futex,
+		atomic: Atomic_Sema,
 	}
 
 	_sema_post :: proc(s: ^Sema, count := 1) {
-		atomic_add_explicit(&s.impl.count, Futex(count), .Release)
-		if count == 1 {
-			futex_signal(&s.impl.count)
-		} else {
-			futex_broadcast(&s.impl.count)
-		}
+		atomic_sema_post(&s.impl.atomic, count)
 	}
 
 	_sema_wait :: proc(s: ^Sema) {
-		for {
-			original_count := atomic_load_explicit(&s.impl.count, .Relaxed)
-			for original_count == 0 {
-				futex_wait(&s.impl.count, u32(original_count))
-				original_count = s.impl.count
-			}
-			if original_count == atomic_compare_exchange_strong_explicit(&s.impl.count, original_count, original_count-1, .Acquire, .Acquire) {
-				return
-			}
-		}
+		atomic_sema_wait(&s.impl.atomic)
 	}
 
 	_sema_wait_with_timeout :: proc(s: ^Sema, duration: time.Duration) -> bool {
-		if duration <= 0 {
-			return false
-		}
-		for {
-		
-			original_count := atomic_load_explicit(&s.impl.count, .Relaxed)
-			for start := time.tick_now(); original_count == 0; /**/ {
-				remaining := duration - time.tick_since(start)
-				if remaining < 0 {
-					return false
-				}
-				
-				if !futex_wait_with_timeout(&s.impl.count, u32(original_count), remaining) {
-					return false
-				}
-				original_count = s.impl.count
-			}
-			if original_count == atomic_compare_exchange_strong_explicit(&s.impl.count, original_count, original_count-1, .Acquire, .Acquire) {
-				return true
-			}
-		}
+		return atomic_sema_wait_with_timeout(&s.impl.atomic, duration)
 	}
 } else {
 	_Sema :: struct {
diff --git a/src/check_builtin.cpp b/src/check_builtin.cpp
index 6c7972d45..9a5d1c554 100644
--- a/src/check_builtin.cpp
+++ b/src/check_builtin.cpp
@@ -29,6 +29,7 @@ BuiltinTypeIsProc *builtin_type_is_procs[BuiltinProc__type_simple_boolean_end -
 
 	is_type_named,
 	is_type_pointer,
+	is_type_multi_pointer,
 	is_type_array,
 	is_type_enumerated_array,
 	is_type_slice,
@@ -3866,6 +3867,7 @@ bool check_builtin_procedure(CheckerContext *c, Operand *operand, Ast *call, i32
 	case BuiltinProc_type_is_valid_matrix_elements:
 	case BuiltinProc_type_is_named:
 	case BuiltinProc_type_is_pointer:
+	case BuiltinProc_type_is_multi_pointer:
 	case BuiltinProc_type_is_array:
 	case BuiltinProc_type_is_enumerated_array:
 	case BuiltinProc_type_is_slice:
diff --git a/src/checker_builtin_procs.hpp b/src/checker_builtin_procs.hpp
index 0f72f01f7..d301cae0c 100644
--- a/src/checker_builtin_procs.hpp
+++ b/src/checker_builtin_procs.hpp
@@ -158,6 +158,7 @@ BuiltinProc__type_simple_boolean_begin,
 
 	BuiltinProc_type_is_named,
 	BuiltinProc_type_is_pointer,
+	BuiltinProc_type_is_multi_pointer,
 	BuiltinProc_type_is_array,
 	BuiltinProc_type_is_enumerated_array,
 	BuiltinProc_type_is_slice,
@@ -376,6 +377,7 @@ gb_global BuiltinProc builtin_procs[BuiltinProc_COUNT] = {
 
 	{STR_LIT("type_is_named"),             1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
 	{STR_LIT("type_is_pointer"),           1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
+	{STR_LIT("type_is_multi_pointer"),      1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
 	{STR_LIT("type_is_array"),             1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
 	{STR_LIT("type_is_enumerated_array"),  1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
 	{STR_LIT("type_is_slice"),             1, false, Expr_Expr, BuiltinProcPkg_intrinsics},
diff --git a/tests/core/download_assets.py b/tests/core/download_assets.py
index d86f7f1e7..50137f563 100644
--- a/tests/core/download_assets.py
+++ b/tests/core/download_assets.py
@@ -5,8 +5,9 @@ import sys
 import os
 import zipfile
 
+TEST_SUITES        = ['PNG', 'XML']
 DOWNLOAD_BASE_PATH = "assets/{}"
-ASSETS_BASE_URL    = "https://raw.githubusercontent.com/Kelimion/compress-odin/master/tests/assets/{}/{}"
+ASSETS_BASE_URL    = "https://raw.githubusercontent.com/odin-lang/test-assets/master/{}/{}"
 PNG_IMAGES         = [
 	"basi0g01.png", "basi0g02.png", "basi0g04.png", "basi0g08.png", "basi0g16.png", "basi2c08.png",
 	"basi2c16.png", "basi3p01.png", "basi3p02.png", "basi3p04.png", "basi3p08.png", "basi4a08.png",
@@ -73,25 +74,27 @@ def try_download_and_unpack_zip(suite):
 		print("Could not extract ZIP file")
 		return 2
 
-
 def main():
-	print("Downloading PNG assets")
+	for suite in TEST_SUITES:
+		print("Downloading {} assets".format(suite))
 
-	# Make PNG assets path
-	try:
-		path = DOWNLOAD_BASE_PATH.format("PNG")
-		os.makedirs(path)
-	except FileExistsError:
-		pass
+		# Make assets path
+		try:
+			path = DOWNLOAD_BASE_PATH.format(suite)
+			os.makedirs(path)
+		except FileExistsError:
+			pass
+
+		# Try downloading and unpacking the assets
+		r = try_download_and_unpack_zip(suite)
+		if r is not None:
+			return r
+
+		# We could fall back on downloading the PNG files individually, but it's slow
+		print("Done downloading {} assets.".format(suite))
 
-	# Try downloading and unpacking the PNG assets
-	r = try_download_and_unpack_zip("PNG")
-	if r is not None:
-		return r
 
-	# We could fall back on downloading the PNG files individually, but it's slow
 
-	print("Done downloading PNG assets")
 	return 0
 
 if __name__ == '__main__':