Subset and superset operators for `bit_set`: < <= > >=

6 files changed, 127 insertions, 15 deletions

diff --git a/core/mem/mem.odin b/core/mem/mem.odin
index f4ecdf9a4..271d30531 100644
--- a/core/mem/mem.odin
+++ b/core/mem/mem.odin
@@ -67,12 +67,41 @@ copy_non_overlapping :: proc "contextless" (dst, src: rawptr, len: int) -> rawpt
 compare :: proc "contextless" (a, b: []byte) -> int {
 	return compare_byte_ptrs(&a[0], &b[0], min(len(a), len(b)));
 }
-compare_byte_ptrs :: proc "contextless" (a, b: ^byte, n: int) -> int {
-	pa :: ptr_offset;
-	for i in 0..n-1 do switch {
-	case pa(a, i)^ < pa(b, i)^: return -1;
-	case pa(a, i)^ > pa(b, i)^: return +1;
+compare_byte_ptrs :: proc "contextless" (a, b: ^byte, n: int) -> int #no_bounds_check {
+	ptr_idx :: inline proc(ptr: $P/^$T, n: int) -> T {
+		return ptr_offset(ptr, n)^;
 	}
+
+	x := slice_ptr(a, n);
+	y := slice_ptr(b, n);
+
+	SU :: size_of(uintptr);
+	fast := n/SU + 1;
+	offset := (fast-1)*SU;
+	curr_block := 0;
+	if n < SU {
+		fast = 0;
+	}
+
+	la := slice_ptr((^uintptr)(a), fast);
+	lb := slice_ptr((^uintptr)(b), fast);
+
+	for /**/; curr_block < fast; curr_block += 1 {
+		if la[curr_block] ~ lb[curr_block] != 0 {
+			for pos := curr_block*SU; pos < n; pos += 1 {
+				if x[pos] ~ y[pos] != 0 {
+					return (int(x[pos]) - int(y[pos])) < 0 ? -1 : +1;
+				}
+			}
+		}
+	}
+
+	for /**/; offset < n; offset += 1 {
+		if x[offset] ~ y[offset] != 0 {
+			return (int(x[offset]) - int(y[offset])) < 0 ? -1 : +1;
+		}
+	}
+
 	return 0;
 }
 
diff --git a/core/runtime/internal.odin b/core/runtime/internal.odin
index 3380412d7..96ff861b2 100644
--- a/core/runtime/internal.odin
+++ b/core/runtime/internal.odin
@@ -22,13 +22,13 @@ print_u64 :: proc(fd: os.Handle, u: u64) {
 
 print_i64 :: proc(fd: os.Handle, u: i64) {
 	digits := "0123456789";
+	b :: i64(10);
 
 	neg := u < 0;
 	u = abs(u);
 
 	a: [129]byte;
 	i := len(a);
-	b := i64(10);
 	for u >= b {
 		i -= 1; a[i] = digits[u % b];
 		u /= b;
diff --git a/examples/demo/demo.odin b/examples/demo/demo.odin
index 1a4b48037..b1aa4e12d 100644
--- a/examples/demo/demo.odin
+++ b/examples/demo/demo.odin
@@ -814,6 +814,21 @@ bit_set_type :: proc() {
 		y |= {1, 4, 2};
 		assert(2 in y);
 	}
+	{
+		Letters :: bit_set['A'..'Z'];
+		a := Letters{'A', 'B'};
+		b := Letters{'A', 'B', 'C', 'D', 'F'};
+		c := Letters{'A', 'B'};
+
+
+		assert(a <= b); // 'a' is a subset of 'b'
+		assert(b >= a); // 'b' is a superset of 'a'
+		assert(a < b);  // 'a' is a strict subset of 'b'
+		assert(b > a);  // 'b' is a strict superset of 'a'
+
+		assert(!(a < c)); // 'a' is a not strict subset of 'c'
+		assert(!(c > a)); // 'c' is a not strict superset of 'a'
+	}
 }
 
 diverging_procedures :: proc() {
diff --git a/src/check_expr.cpp b/src/check_expr.cpp
index cb54f6b7a..47b741f40 100644
--- a/src/check_expr.cpp
+++ b/src/check_expr.cpp
@@ -1558,7 +1558,11 @@ void check_comparison(CheckerContext *c, Operand *x, Operand *y, TokenKind op) {
 		case Token_Gt:
 		case Token_LtEq:
 		case Token_GtEq:
-			defined = is_type_ordered(x->type) && is_type_ordered(y->type);
+			if (are_types_identical(x->type, y->type) && is_type_bit_set(x->type)) {
+				defined = true;
+			} else {
+				defined = is_type_ordered(x->type) && is_type_ordered(y->type);
+			}
 			break;
 		}
 
@@ -1596,7 +1600,42 @@ void check_comparison(CheckerContext *c, Operand *x, Operand *y, TokenKind op) {
 		if (x->mode == Addressing_Constant &&
 		    y->mode == Addressing_Constant) {
 			if (is_type_constant_type(x->type)) {
-				x->value = exact_value_bool(compare_exact_values(op, x->value, y->value));
+				if (is_type_bit_set(x->type)) {
+					switch (op) {
+					case Token_CmpEq:
+					case Token_NotEq:
+						x->value = exact_value_bool(compare_exact_values(op, x->value, y->value));
+						break;
+					case Token_Lt:
+					case Token_LtEq:
+						{
+							ExactValue lhs = x->value;
+							ExactValue rhs = y->value;
+							ExactValue res = exact_binary_operator_value(Token_And, lhs, rhs);
+							res = exact_value_bool(compare_exact_values(op, res, lhs));
+							if (op == Token_Lt) {
+								res = exact_binary_operator_value(Token_And, res, exact_value_bool(compare_exact_values(op, lhs, rhs)));
+							}
+							x->value = res;
+							break;
+						}
+					case Token_Gt:
+					case Token_GtEq:
+						{
+							ExactValue lhs = x->value;
+							ExactValue rhs = y->value;
+							ExactValue res = exact_binary_operator_value(Token_And, lhs, rhs);
+							res = exact_value_bool(compare_exact_values(op, res, rhs));
+							if (op == Token_Gt) {
+								res = exact_binary_operator_value(Token_And, res, exact_value_bool(compare_exact_values(op, lhs, rhs)));
+							}
+							x->value = res;
+							break;
+						}
+					}
+				} else {
+					x->value = exact_value_bool(compare_exact_values(op, x->value, y->value));
+				}
 			} else {
 				x->mode = Addressing_Value;
 			}
@@ -2084,8 +2123,8 @@ void check_binary_expr(CheckerContext *c, Operand *x, Ast *node, bool use_lhs_as
 			add_package_dependency(c, "runtime", "__dynamic_map_get");
 		} else if (is_type_bit_set(y->type)) {
 			Type *yt = base_type(y->type);
-			check_assignment(c, x, yt->BitSet.elem, str_lit("bit_set 'in'"));
 
+			check_assignment(c, x, yt->BitSet.elem, str_lit("bit_set 'in'"));
 			if (x->mode == Addressing_Constant && y->mode == Addressing_Constant) {
 				ExactValue k = exact_value_to_integer(x->value);
 				ExactValue v = exact_value_to_integer(y->value);
@@ -2109,7 +2148,6 @@ void check_binary_expr(CheckerContext *c, Operand *x, Ast *node, bool use_lhs_as
 					x->mode = Addressing_Invalid;
 				}
 			}
-
 		} else {
 			gbString t = type_to_string(y->type);
 			error(x->expr, "expected either a map or bitset for 'in', got %s", t);
diff --git a/src/entity.cpp b/src/entity.cpp
index 22c7a24f4..707a04962 100644
--- a/src/entity.cpp
+++ b/src/entity.cpp
@@ -85,14 +85,14 @@ struct Entity {
 	Token       token;
 	Scope *     scope;
 	Type *      type;
-	Ast *   identifier; // Can be nullptr
+	Ast *       identifier; // Can be nullptr
 	DeclInfo *  decl_info;
 	DeclInfo *  parent_proc_decl; // nullptr if in file/global scope
 	AstPackage *pkg;
 
 	// TODO(bill): Cleanup how `using` works for entities
 	Entity *    using_parent;
-	Ast *   using_expr;
+	Ast *       using_expr;
 
 	isize       order_in_src;
 	String      deprecated_message;
@@ -109,7 +109,7 @@ struct Entity {
 
 			String     thread_local_model;
 			Entity *   foreign_library;
-			Ast *  foreign_library_ident;
+			Ast *      foreign_library_ident;
 			String     link_name;
 			String     link_prefix;
 			bool       is_foreign;
@@ -117,9 +117,9 @@ struct Entity {
 			bool       is_immutable;
 		} Variable;
 		struct {
-			bool   is_type_alias;
 			Type * type_parameter_specialization;
 			String ir_mangled_name;
+			bool   is_type_alias;
 		} TypeName;
 		struct {
 			u64     tags;
diff --git a/src/ir.cpp b/src/ir.cpp
index 7ee3c9600..618996bcc 100644
--- a/src/ir.cpp
+++ b/src/ir.cpp
@@ -3823,6 +3823,37 @@ irValue *ir_emit_comp(irProcedure *proc, TokenKind op_kind, irValue *left, irVal
 		return ir_emit_runtime_call(proc, runtime_proc, args);
 	}
 
+	if (is_type_bit_set(a)) {
+		switch (op_kind) {
+		case Token_Lt:
+		case Token_LtEq:
+		case Token_Gt:
+		case Token_GtEq:
+			{
+				Type *it = bit_set_to_int(a);
+				irValue *lhs = ir_emit_bitcast(proc, left, it);
+				irValue *rhs = ir_emit_bitcast(proc, right, it);
+				irValue *res = ir_emit_arith(proc, Token_And, lhs, rhs, it);
+
+				if (op_kind == Token_Lt || op_kind == Token_LtEq) {
+					// (lhs & rhs) == lhs
+					res = ir_emit(proc, ir_instr_binary_op(proc, Token_CmpEq, res, lhs, t_llvm_bool));
+				} else if (op_kind == Token_Gt || op_kind == Token_GtEq) {
+					// (lhs & rhs) == rhs
+					res = ir_emit(proc, ir_instr_binary_op(proc, Token_CmpEq, res, rhs, t_llvm_bool));
+				}
+
+				// NOTE(bill): Strict subsets
+				if (op_kind == Token_Lt || op_kind == Token_Gt) {
+					// res &~ (lhs == rhs)
+					irValue *eq = ir_emit(proc, ir_instr_binary_op(proc, Token_CmpEq, lhs, rhs, t_llvm_bool));
+					res = ir_emit_arith(proc, Token_AndNot, res, eq, t_llvm_bool);
+				}
+
+				return res;
+			}
+		}
+	}
 
 	return ir_emit(proc, ir_instr_binary_op(proc, op_kind, left, right, t_llvm_bool));
 }
@@ -6168,7 +6199,6 @@ irValue *ir_build_expr_internal(irProcedure *proc, Ast *expr) {
 
 					Type *key_type = rt->BitSet.elem;
 					GB_ASSERT(are_types_identical(ir_type(left), key_type));
-
 					Type *it = bit_set_to_int(rt);
 					left = ir_emit_conv(proc, left, it);