Merge pull request #3940 from ziglang/sentinel-slicing

fix std.mem.addNullByte and implement sentinel slicing

4 files changed, 158 insertions, 16 deletions

diff --git a/src/all_types.hpp b/src/all_types.hpp
index bcef45f718..ea46ab81a6 100644
--- a/src/all_types.hpp
+++ b/src/all_types.hpp
@@ -810,6 +810,7 @@ struct AstNodeSliceExpr {
     AstNode *array_ref_expr;
     AstNode *start;
     AstNode *end;
+    AstNode *sentinel; // can be null
 };
 
 struct AstNodeFieldAccessExpr {
@@ -1778,6 +1779,7 @@ enum PanicMsgId {
     PanicMsgIdResumedFnPendingAwait,
     PanicMsgIdBadNoAsyncCall,
     PanicMsgIdResumeNotSuspendedFn,
+    PanicMsgIdBadSentinel,
 
     PanicMsgIdCount,
 };
@@ -3388,6 +3390,7 @@ struct IrInstructionSliceSrc {
     IrInstruction *ptr;
     IrInstruction *start;
     IrInstruction *end;
+    IrInstruction *sentinel;
     ResultLoc *result_loc;
 };
 
diff --git a/src/codegen.cpp b/src/codegen.cpp
index edc2c7f435..1455b4b743 100644
--- a/src/codegen.cpp
+++ b/src/codegen.cpp
@@ -941,6 +941,8 @@ static Buf *panic_msg_buf(PanicMsgId msg_id) {
             return buf_create_from_str("async function called with noasync suspended");
         case PanicMsgIdResumeNotSuspendedFn:
             return buf_create_from_str("resumed a non-suspended function");
+        case PanicMsgIdBadSentinel:
+            return buf_create_from_str("sentinel mismatch");
     }
     zig_unreachable();
 }
@@ -1419,6 +1421,27 @@ static void add_bounds_check(CodeGen *g, LLVMValueRef target_val,
     LLVMPositionBuilderAtEnd(g->builder, ok_block);
 }
 
+static void add_sentinel_check(CodeGen *g, LLVMValueRef sentinel_elem_ptr, ZigValue *sentinel) {
+    LLVMValueRef expected_sentinel = gen_const_val(g, sentinel, "");
+
+    LLVMValueRef actual_sentinel = gen_load_untyped(g, sentinel_elem_ptr, 0, false, "");
+    LLVMValueRef ok_bit;
+    if (sentinel->type->id == ZigTypeIdFloat) {
+        ok_bit = LLVMBuildFCmp(g->builder, LLVMRealOEQ, actual_sentinel, expected_sentinel, "");
+    } else {
+        ok_bit = LLVMBuildICmp(g->builder, LLVMIntEQ, actual_sentinel, expected_sentinel, "");
+    }
+
+    LLVMBasicBlockRef fail_block = LLVMAppendBasicBlock(g->cur_fn_val, "SentinelFail");
+    LLVMBasicBlockRef ok_block = LLVMAppendBasicBlock(g->cur_fn_val, "SentinelOk");
+    LLVMBuildCondBr(g->builder, ok_bit, ok_block, fail_block);
+
+    LLVMPositionBuilderAtEnd(g->builder, fail_block);
+    gen_safety_crash(g, PanicMsgIdBadSentinel);
+
+    LLVMPositionBuilderAtEnd(g->builder, ok_block);
+}
+
 static LLVMValueRef gen_assert_zero(CodeGen *g, LLVMValueRef expr_val, ZigType *int_type) {
     LLVMValueRef zero = LLVMConstNull(get_llvm_type(g, int_type));
     LLVMValueRef ok_bit = LLVMBuildICmp(g->builder, LLVMIntEQ, expr_val, zero, "");
@@ -5244,6 +5267,9 @@ static LLVMValueRef ir_render_slice(CodeGen *g, IrExecutable *executable, IrInst
 
     bool want_runtime_safety = instruction->safety_check_on && ir_want_runtime_safety(g, &instruction->base);
 
+    ZigType *res_slice_ptr_type = instruction->base.value->type->data.structure.fields[slice_ptr_index]->type_entry;
+    ZigValue *sentinel = res_slice_ptr_type->data.pointer.sentinel;
+
     if (array_type->id == ZigTypeIdArray ||
         (array_type->id == ZigTypeIdPointer && array_type->data.pointer.ptr_len == PtrLenSingle))
     {
@@ -5265,6 +5291,15 @@ static LLVMValueRef ir_render_slice(CodeGen *g, IrExecutable *executable, IrInst
                 LLVMValueRef array_end = LLVMConstInt(g->builtin_types.entry_usize->llvm_type,
                         array_type->data.array.len, false);
                 add_bounds_check(g, end_val, LLVMIntEQ, nullptr, LLVMIntULE, array_end);
+
+                if (sentinel != nullptr) {
+                    LLVMValueRef indices[] = {
+                        LLVMConstNull(g->builtin_types.entry_usize->llvm_type),
+                        end_val,
+                    };
+                    LLVMValueRef sentinel_elem_ptr = LLVMBuildInBoundsGEP(g->builder, array_ptr, indices, 2, "");
+                    add_sentinel_check(g, sentinel_elem_ptr, sentinel);
+                }
             }
         }
         if (!type_has_bits(array_type)) {
@@ -5297,6 +5332,10 @@ static LLVMValueRef ir_render_slice(CodeGen *g, IrExecutable *executable, IrInst
 
         if (want_runtime_safety) {
             add_bounds_check(g, start_val, LLVMIntEQ, nullptr, LLVMIntULE, end_val);
+            if (sentinel != nullptr) {
+                LLVMValueRef sentinel_elem_ptr = LLVMBuildInBoundsGEP(g->builder, array_ptr, &end_val, 1, "");
+                add_sentinel_check(g, sentinel_elem_ptr, sentinel);
+            }
         }
 
         if (type_has_bits(array_type)) {
@@ -5337,18 +5376,24 @@ static LLVMValueRef ir_render_slice(CodeGen *g, IrExecutable *executable, IrInst
             end_val = prev_end;
         }
 
+        LLVMValueRef src_ptr_ptr = LLVMBuildStructGEP(g->builder, array_ptr, (unsigned)ptr_index, "");
+        LLVMValueRef src_ptr = gen_load_untyped(g, src_ptr_ptr, 0, false, "");
+
         if (want_runtime_safety) {
             assert(prev_end);
             add_bounds_check(g, start_val, LLVMIntEQ, nullptr, LLVMIntULE, end_val);
             if (instruction->end) {
                 add_bounds_check(g, end_val, LLVMIntEQ, nullptr, LLVMIntULE, prev_end);
+
+                if (sentinel != nullptr) {
+                    LLVMValueRef sentinel_elem_ptr = LLVMBuildInBoundsGEP(g->builder, src_ptr, &end_val, 1, "");
+                    add_sentinel_check(g, sentinel_elem_ptr, sentinel);
+                }
             }
         }
 
-        LLVMValueRef src_ptr_ptr = LLVMBuildStructGEP(g->builder, array_ptr, (unsigned)ptr_index, "");
-        LLVMValueRef src_ptr = gen_load_untyped(g, src_ptr_ptr, 0, false, "");
         LLVMValueRef ptr_field_ptr = LLVMBuildStructGEP(g->builder, tmp_struct_ptr, (unsigned)ptr_index, "");
-        LLVMValueRef slice_start_ptr = LLVMBuildInBoundsGEP(g->builder, src_ptr, &start_val, (unsigned)len_index, "");
+        LLVMValueRef slice_start_ptr = LLVMBuildInBoundsGEP(g->builder, src_ptr, &start_val, 1, "");
         gen_store_untyped(g, slice_start_ptr, ptr_field_ptr, 0, false);
 
         LLVMValueRef len_field_ptr = LLVMBuildStructGEP(g->builder, tmp_struct_ptr, (unsigned)len_index, "");
diff --git a/src/ir.cpp b/src/ir.cpp
index 3000269ad3..d60fe9ea70 100644
--- a/src/ir.cpp
+++ b/src/ir.cpp
@@ -2967,18 +2967,21 @@ static IrInstruction *ir_build_memcpy(IrBuilder *irb, Scope *scope, AstNode *sou
 }
 
 static IrInstruction *ir_build_slice_src(IrBuilder *irb, Scope *scope, AstNode *source_node,
-    IrInstruction *ptr, IrInstruction *start, IrInstruction *end, bool safety_check_on, ResultLoc *result_loc)
+    IrInstruction *ptr, IrInstruction *start, IrInstruction *end, IrInstruction *sentinel,
+    bool safety_check_on, ResultLoc *result_loc)
 {
     IrInstructionSliceSrc *instruction = ir_build_instruction<IrInstructionSliceSrc>(irb, scope, source_node);
     instruction->ptr = ptr;
     instruction->start = start;
     instruction->end = end;
+    instruction->sentinel = sentinel;
     instruction->safety_check_on = safety_check_on;
     instruction->result_loc = result_loc;
 
     ir_ref_instruction(ptr, irb->current_basic_block);
     ir_ref_instruction(start, irb->current_basic_block);
     if (end) ir_ref_instruction(end, irb->current_basic_block);
+    if (sentinel) ir_ref_instruction(sentinel, irb->current_basic_block);
 
     return &instruction->base;
 }
@@ -8483,6 +8486,7 @@ static IrInstruction *ir_gen_slice(IrBuilder *irb, Scope *scope, AstNode *node,
     AstNode *array_node = slice_expr->array_ref_expr;
     AstNode *start_node = slice_expr->start;
     AstNode *end_node = slice_expr->end;
+    AstNode *sentinel_node = slice_expr->sentinel;
 
     IrInstruction *ptr_value = ir_gen_node_extra(irb, array_node, scope, LValPtr, nullptr);
     if (ptr_value == irb->codegen->invalid_instruction)
@@ -8501,7 +8505,17 @@ static IrInstruction *ir_gen_slice(IrBuilder *irb, Scope *scope, AstNode *node,
         end_value = nullptr;
     }
 
-    IrInstruction *slice = ir_build_slice_src(irb, scope, node, ptr_value, start_value, end_value, true, result_loc);
+    IrInstruction *sentinel_value;
+    if (sentinel_node) {
+        sentinel_value = ir_gen_node(irb, sentinel_node, scope);
+        if (sentinel_value == irb->codegen->invalid_instruction)
+            return irb->codegen->invalid_instruction;
+    } else {
+        sentinel_value = nullptr;
+    }
+
+    IrInstruction *slice = ir_build_slice_src(irb, scope, node, ptr_value, start_value, end_value,
+            sentinel_value, true, result_loc);
     return ir_lval_wrap(irb, scope, slice, lval, result_loc);
 }
 
@@ -10533,6 +10547,18 @@ static ConstCastOnly types_match_const_cast_only(IrAnalyze *ira, ZigType *wanted
             result.id = ConstCastResultIdInvalid;
             return result;
         }
+        bool ok_sentinels =
+            wanted_ptr_type->data.pointer.sentinel == nullptr ||
+            (actual_ptr_type->data.pointer.sentinel != nullptr &&
+             const_values_equal(ira->codegen, wanted_ptr_type->data.pointer.sentinel,
+                 actual_ptr_type->data.pointer.sentinel));
+        if (!ok_sentinels) {
+            result.id = ConstCastResultIdPtrSentinel;
+            result.data.bad_ptr_sentinel = allocate_nonzero<ConstCastPtrSentinel>(1);
+            result.data.bad_ptr_sentinel->wanted_type = wanted_ptr_type;
+            result.data.bad_ptr_sentinel->actual_type = actual_ptr_type;
+            return result;
+        }
         if ((!actual_ptr_type->data.pointer.is_const || wanted_ptr_type->data.pointer.is_const) &&
             (!actual_ptr_type->data.pointer.is_volatile || wanted_ptr_type->data.pointer.is_volatile) &&
             actual_ptr_type->data.pointer.bit_offset_in_host == wanted_ptr_type->data.pointer.bit_offset_in_host &&
@@ -14441,6 +14467,32 @@ static bool optional_value_is_null(ZigValue *val) {
     }
 }
 
+static void set_optional_value_to_null(ZigValue *val) {
+    assert(val->special == ConstValSpecialStatic);
+    if (val->type->id == ZigTypeIdNull) return; // nothing to do
+    assert(val->type->id == ZigTypeIdOptional);
+    if (get_codegen_ptr_type(val->type) != nullptr) {
+        val->data.x_ptr.special = ConstPtrSpecialNull;
+    } else if (is_opt_err_set(val->type)) {
+        val->data.x_err_set = nullptr;
+    } else {
+        val->data.x_optional = nullptr;
+    }
+}
+
+static void set_optional_payload(ZigValue *opt_val, ZigValue *payload) {
+    assert(opt_val->special == ConstValSpecialStatic);
+    assert(opt_val->type->id == ZigTypeIdOptional);
+    if (payload == nullptr) {
+        set_optional_value_to_null(opt_val);
+    } else if (is_opt_err_set(opt_val->type)) {
+        assert(payload->type->id == ZigTypeIdErrorSet);
+        opt_val->data.x_err_set = payload->data.x_err_set;
+    } else {
+        opt_val->data.x_optional = payload;
+    }
+}
+
 static IrInstruction *ir_evaluate_bin_op_cmp(IrAnalyze *ira, ZigType *resolved_type,
     ZigValue *op1_val, ZigValue *op2_val, IrInstructionBinOp *bin_op_instruction, IrBinOp op_id,
     bool one_possible_value) {
@@ -19313,6 +19365,20 @@ static ZigType *adjust_ptr_align(CodeGen *g, ZigType *ptr_type, uint32_t new_ali
             ptr_type->data.pointer.sentinel);
 }
 
+static ZigType *adjust_ptr_sentinel(CodeGen *g, ZigType *ptr_type, ZigValue *new_sentinel) {
+    assert(ptr_type->id == ZigTypeIdPointer);
+    return get_pointer_to_type_extra2(g,
+            ptr_type->data.pointer.child_type,
+            ptr_type->data.pointer.is_const, ptr_type->data.pointer.is_volatile,
+            ptr_type->data.pointer.ptr_len,
+            ptr_type->data.pointer.explicit_alignment,
+            ptr_type->data.pointer.bit_offset_in_host, ptr_type->data.pointer.host_int_bytes,
+            ptr_type->data.pointer.allow_zero,
+            ptr_type->data.pointer.vector_index,
+            ptr_type->data.pointer.inferred_struct_field,
+            new_sentinel);
+}
+
 static ZigType *adjust_slice_align(CodeGen *g, ZigType *slice_type, uint32_t new_align) {
     assert(is_slice(slice_type));
     ZigType *ptr_type = adjust_ptr_align(g, slice_type->data.structure.fields[slice_ptr_index]->type_entry,
@@ -22691,7 +22757,7 @@ static ZigValue *create_ptr_like_type_info(IrAnalyze *ira, ZigType *ptr_type_ent
     fields[6]->special = ConstValSpecialStatic;
     if (attrs_type->data.pointer.child_type->id != ZigTypeIdOpaque) {
         fields[6]->type = get_optional_type(ira->codegen, attrs_type->data.pointer.child_type);
-        fields[6]->data.x_optional = attrs_type->data.pointer.sentinel;
+        set_optional_payload(fields[6], attrs_type->data.pointer.sentinel);
     } else {
         fields[6]->type = ira->codegen->builtin_types.entry_null;
     }
@@ -25051,50 +25117,72 @@ static IrInstruction *ir_analyze_instruction_slice(IrAnalyze *ira, IrInstruction
         end = nullptr;
     }
 
-    ZigType *return_type;
+    ZigType *non_sentinel_slice_ptr_type;
+    ZigType *elem_type;
 
     if (array_type->id == ZigTypeIdArray) {
+        elem_type = array_type->data.array.child_type;
         bool is_comptime_const = ptr_ptr->value->special == ConstValSpecialStatic &&
             ptr_ptr->value->data.x_ptr.mut == ConstPtrMutComptimeConst;
-        ZigType *slice_ptr_type = get_pointer_to_type_extra(ira->codegen, array_type->data.array.child_type,
+        non_sentinel_slice_ptr_type = get_pointer_to_type_extra(ira->codegen, elem_type,
             ptr_ptr_type->data.pointer.is_const || is_comptime_const,
             ptr_ptr_type->data.pointer.is_volatile,
             PtrLenUnknown,
             ptr_ptr_type->data.pointer.explicit_alignment, 0, 0, false);
-        return_type = get_slice_type(ira->codegen, slice_ptr_type);
     } else if (array_type->id == ZigTypeIdPointer) {
         if (array_type->data.pointer.ptr_len == PtrLenSingle) {
             ZigType *main_type = array_type->data.pointer.child_type;
             if (main_type->id == ZigTypeIdArray) {
-                ZigType *slice_ptr_type = get_pointer_to_type_extra(ira->codegen,
-                        main_type->data.pointer.child_type,
+                elem_type = main_type->data.pointer.child_type;
+                non_sentinel_slice_ptr_type = get_pointer_to_type_extra(ira->codegen,
+                        elem_type,
                         array_type->data.pointer.is_const, array_type->data.pointer.is_volatile,
                         PtrLenUnknown,
                         array_type->data.pointer.explicit_alignment, 0, 0, false);
-                return_type = get_slice_type(ira->codegen, slice_ptr_type);
             } else {
                 ir_add_error(ira, &instruction->base, buf_sprintf("slice of single-item pointer"));
                 return ira->codegen->invalid_instruction;
             }
         } else {
+            elem_type = array_type->data.pointer.child_type;
             if (array_type->data.pointer.ptr_len == PtrLenC) {
                 array_type = adjust_ptr_len(ira->codegen, array_type, PtrLenUnknown);
             }
-            return_type = get_slice_type(ira->codegen, array_type);
+            ZigType *maybe_sentineled_slice_ptr_type = array_type;
+            non_sentinel_slice_ptr_type = adjust_ptr_sentinel(ira->codegen, maybe_sentineled_slice_ptr_type, nullptr);
             if (!end) {
                 ir_add_error(ira, &instruction->base, buf_sprintf("slice of pointer must include end value"));
                 return ira->codegen->invalid_instruction;
             }
         }
     } else if (is_slice(array_type)) {
-        ZigType *ptr_type = array_type->data.structure.fields[slice_ptr_index]->type_entry;
-        return_type = get_slice_type(ira->codegen, ptr_type);
+        ZigType *maybe_sentineled_slice_ptr_type = array_type->data.structure.fields[slice_ptr_index]->type_entry;
+        non_sentinel_slice_ptr_type = adjust_ptr_sentinel(ira->codegen, maybe_sentineled_slice_ptr_type, nullptr);
+        elem_type = non_sentinel_slice_ptr_type->data.pointer.child_type;
     } else {
         ir_add_error(ira, &instruction->base,
             buf_sprintf("slice of non-array type '%s'", buf_ptr(&array_type->name)));
         return ira->codegen->invalid_instruction;
     }
 
+    ZigType *return_type;
+    ZigValue *sentinel_val = nullptr;
+    if (instruction->sentinel) {
+        IrInstruction *uncasted_sentinel = instruction->sentinel->child;
+        if (type_is_invalid(uncasted_sentinel->value->type))
+            return ira->codegen->invalid_instruction;
+        IrInstruction *sentinel = ir_implicit_cast(ira, uncasted_sentinel, elem_type);
+        if (type_is_invalid(sentinel->value->type))
+            return ira->codegen->invalid_instruction;
+        sentinel_val = ir_resolve_const(ira, sentinel, UndefBad);
+        if (sentinel_val == nullptr)
+            return ira->codegen->invalid_instruction;
+        ZigType *slice_ptr_type = adjust_ptr_sentinel(ira->codegen, non_sentinel_slice_ptr_type, sentinel_val);
+        return_type = get_slice_type(ira->codegen, slice_ptr_type);
+    } else {
+        return_type = get_slice_type(ira->codegen, non_sentinel_slice_ptr_type);
+    }
+
     if (instr_is_comptime(ptr_ptr) &&
         value_is_comptime(casted_start->value) &&
         (!end || value_is_comptime(end->value)))
diff --git a/src/parser.cpp b/src/parser.cpp
index 4b5e0e3ebb..a0c5cf794b 100644
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -2723,7 +2723,7 @@ static AstNode *ast_parse_prefix_type_op(ParseContext *pc) {
 }
 
 // SuffixOp
-//     <- LBRACKET Expr (DOT2 Expr?)? RBRACKET
+//     <- LBRACKET Expr (DOT2 (Expr (COLON Expr)?)?)? RBRACKET
 //      / DOT IDENTIFIER
 //      / DOTASTERISK
 //      / DOTQUESTIONMARK
@@ -2733,12 +2733,17 @@ static AstNode *ast_parse_suffix_op(ParseContext *pc) {
         AstNode *start = ast_expect(pc, ast_parse_expr);
         AstNode *end = nullptr;
         if (eat_token_if(pc, TokenIdEllipsis2) != nullptr) {
+            AstNode *sentinel = nullptr;
             end = ast_parse_expr(pc);
+            if (eat_token_if(pc, TokenIdColon) != nullptr) {
+                sentinel = ast_parse_expr(pc);
+            }
             expect_token(pc, TokenIdRBracket);
 
             AstNode *res = ast_create_node(pc, NodeTypeSliceExpr, lbracket);
             res->data.slice_expr.start = start;
             res->data.slice_expr.end = end;
+            res->data.slice_expr.sentinel = sentinel;
             return res;
         }
 
@@ -3041,6 +3046,7 @@ void ast_visit_node_children(AstNode *node, void (*visit)(AstNode **, void *cont
             visit_field(&node->data.slice_expr.array_ref_expr, visit, context);
             visit_field(&node->data.slice_expr.start, visit, context);
             visit_field(&node->data.slice_expr.end, visit, context);
+            visit_field(&node->data.slice_expr.sentinel, visit, context);
             break;
         case NodeTypeFieldAccessExpr:
             visit_field(&node->data.field_access_expr.struct_expr, visit, context);