fix(arrays): reject inverted bounds and check array allocation

Constant inverted bounds are a compile error and other bounds are checked
at run time. Allocation sizes use overflow-checked arithmetic, and a NULL
malloc (including the BYVAL copy) reports that the array is too large.

Co-Authored-By: Claude Sonnet 5.5 <noreply@anthropic.com>

6 files changed, 77 insertions, 2 deletions

diff --git a/AGENTS/SUBSYSTEMS/ARRAYS.md b/AGENTS/SUBSYSTEMS/ARRAYS.md
index 188ff5b..cc104a5 100644
--- a/AGENTS/SUBSYSTEMS/ARRAYS.md
+++ b/AGENTS/SUBSYSTEMS/ARRAYS.md
@@ -10,6 +10,10 @@ parameter binding/arguments in `ArrayParameters.cc`, and output in `ArrayOutput.
 
 - A DECLAREd array is one malloc'd flat buffer (memset to zero), row-major, any rank,
   any bounds.
+- Every dimension needs `upper >= lower`: constant bounds are a compile error, other
+  bounds a runtime error (`emitCheckedByteSize`). The byte size is computed with
+  `llvm.{ssub,umul}.with.overflow`; overflow or a NULL malloc (also the BYVAL copy)
+  reports `Array X is too large`. Arrays therefore always have at least one element.
 - Bounds and multipliers are *SSA values* cached in `ArrayMetadata`.
 - `ArrayTable` is scoped per function (`exchangeTable`, driven from CodeGen's
   `FunctionDefAST` branch, mirroring the Symbols discipline).
diff --git a/doc/language/keyword/cpsc-keyword-declare.7.md b/doc/language/keyword/cpsc-keyword-declare.7.md
index 6138916..6860ff5 100644
--- a/doc/language/keyword/cpsc-keyword-declare.7.md
+++ b/doc/language/keyword/cpsc-keyword-declare.7.md
@@ -17,7 +17,7 @@ Declare one variable per statement. Built-in types are INTEGER (signed 64-bit),
 
 C_INT, C_CHAR, C_STRING and C_DOUBLE are native C aliases for int, char, char* and double. C_TYPE can introduce aliases for other supported C base types and pointers. C values start with zero or null; assignment from pseudocode types requires an explicit cast. See [cpsc-keyword-c_type(7)](cpsc-keyword-c_type.7.md).
 
-ARRAY bounds are inclusive and may be expressions; multiple ranges create multiple dimensions. Access elements with `name[index, ...]`. Bounds are checked at run time; an invalid index throws an exception that TRY/CATCH can handle. Whole-array assignment is unsupported. Declare arrays before using them; arrays declared inside a control-flow block stay in that block.
+ARRAY bounds are inclusive and may be expressions; every dimension needs an upper bound that is at least the lower bound (constant bounds that are inverted are a compile error, other bounds a run-time error), and an array too large to allocate is a run-time error; multiple ranges create multiple dimensions. Access elements with `name[index, ...]`. Bounds are checked at run time; an invalid index throws an exception that TRY/CATCH can handle. Whole-array assignment is unsupported. Declare arrays before using them; arrays declared inside a control-flow block stay in that block.
 
 For class variables, an optional argument list after the type supplies constructor arguments, such as `DECLARE Item : Counter(3)`. Declarations zero storage and automatically construct class fields and array elements before calling the outer constructor. See [cpsc-keyword-class(7)](cpsc-keyword-class.7.md) for construction and NEW rebinding rules.
 
diff --git a/include/cps/ArrayHandler.h b/include/cps/ArrayHandler.h
index a09e708..f2d3490 100644
--- a/include/cps/ArrayHandler.h
+++ b/include/cps/ArrayHandler.h
@@ -52,6 +52,15 @@ class ArrayHandler {
                                         std::vector<llvm::Value*> Lows,
                                         std::vector<llvm::Value*> Highs,
                                         llvm::Value *&TotalElements);
+    // Validates every dimension (upper >= lower) and returns the allocation
+    // size in bytes, trapping on overflow. Constant bounds were already checked
+    // at compile time; the others get a runtime check.
+    llvm::Value *emitCheckedByteSize(const std::string &Name,
+                                     const std::vector<llvm::Value*> &Lows,
+                                     const std::vector<llvm::Value*> &Highs,
+                                     llvm::Constant *ElementSize, int Line);
+    // Traps with "Array NAME is too large" when Ptr (a malloc result) is null.
+    void emitAllocCheck(llvm::Value *Ptr, const std::string &Name, int Line);
     bool emitCheckedIndices(const std::string &Name,
                             const std::vector<std::unique_ptr<ExprAST>> &IndexExprs,
                             int Line,
diff --git a/lib/CodeGen/ArrayHandler.cc b/lib/CodeGen/ArrayHandler.cc
index de07ff7..a4cbbe4 100644
--- a/lib/CodeGen/ArrayHandler.cc
+++ b/lib/CodeGen/ArrayHandler.cc
@@ -1,4 +1,5 @@
 #include "cps/ArrayHandler.h"
+#include "llvm/IR/Intrinsics.h"
 #include "cps/CodeGen.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
@@ -108,6 +109,15 @@ void ArrayHandler::emitArrayDeclare(ArrayDeclareStmtAST *Stmt, CodeGen &CG) {
 
         if (!L || !R) return;
 
+        auto *ConstL = dyn_cast<ConstantInt>(L);
+        auto *ConstR = dyn_cast<ConstantInt>(R);
+        if (ConstL && ConstR && ConstR->getSExtValue() < ConstL->getSExtValue()) {
+            CG.reportError("Array %s upper bound %lld is less than lower bound %lld", Name.c_str(),
+                           static_cast<long long>(ConstR->getSExtValue()),
+                           static_cast<long long>(ConstL->getSExtValue()));
+            return;
+        }
+
         Lows.push_back(L);
         Highs.push_back(R);
     }
@@ -116,8 +126,10 @@ void ArrayHandler::emitArrayDeclare(ArrayDeclareStmtAST *Stmt, CodeGen &CG) {
     const ArrayMetadata &Meta =
         defineMetadata(Name, ElemInfo, std::move(Lows), std::move(Highs), TotalElements);
 
-    Value *TotalBytes = Builder->CreateMul(TotalElements, Meta.ElementSizeC, Name + "_total_bytes");
+    Value *TotalBytes = emitCheckedByteSize(Name, Meta.LowerBounds, Meta.UpperBounds,
+                                            Meta.ElementSizeC, Stmt->getLine());
     CallInst *Ptr = Builder->CreateCall(MallocFunc, TotalBytes, Name + "_malloc");
+    emitAllocCheck(Ptr, Name, Stmt->getLine());
 
     FunctionType *MemsetType = FunctionType::get(PointerType::getUnqual(*TheContext),
                                                  {PointerType::getUnqual(*TheContext), Type::getInt32Ty(*TheContext), Type::getInt64Ty(*TheContext)},
@@ -150,6 +162,53 @@ void ArrayHandler::emitArrayDeclare(ArrayDeclareStmtAST *Stmt, CodeGen &CG) {
     CG.activateStackObject(Lifetime, TotalElements);
 }
 
+Value *ArrayHandler::emitCheckedByteSize(const std::string &Name,
+                                         const std::vector<Value*> &Lows,
+                                         const std::vector<Value*> &Highs,
+                                         Constant *ElementSize, int Line) {
+    Type *I64 = Type::getInt64Ty(*TheContext);
+    Value *NameStr = Builder->CreateGlobalString(Name, "array_name", 0, TheModule);
+    Value *InvalidMsg = Builder->CreateGlobalString(
+        "[Fatal] line %d: Invalid bounds [%lld:%lld] for array %s\n", "err_array_bounds", 0, TheModule);
+    Value *TooLargeMsg = Builder->CreateGlobalString(
+        "[Fatal] line %d: Array %s is too large\n", "err_array_large", 0, TheModule);
+
+    // Pass 1: upper >= lower in every dimension (this also keeps the
+    // differences below non-negative, so only the subtraction can overflow).
+    for (size_t I = 0; I < Lows.size(); ++I) {
+        if (isa<ConstantInt>(Lows[I]) && isa<ConstantInt>(Highs[I])) continue; // checked at compile time
+        Value *Inverted = Builder->CreateICmpSLT(Highs[I], Lows[I], Name + "_inverted");
+        RuntimeChecker.emitCheck(Inverted, InvalidMsg, {RuntimeChecker.lineValue(Line), Lows[I], Highs[I], NameStr});
+    }
+
+    // Pass 2: sizes with overflow detection.
+    auto Overflowing = [&](Intrinsic::ID Id, Value *A, Value *B, Value *&Overflow) {
+        Value *Pair = Builder->CreateBinaryIntrinsic(Id, A, B);
+        Value *Flag = Builder->CreateExtractValue(Pair, 1);
+        Overflow = Overflow ? Builder->CreateOr(Overflow, Flag) : Flag;
+        return Builder->CreateExtractValue(Pair, 0);
+    };
+    Value *Overflow = nullptr;
+    Value *Total = ConstantInt::get(I64, 1);
+    for (size_t I = 0; I < Lows.size(); ++I) {
+        Value *Diff = Overflowing(Intrinsic::ssub_with_overflow, Highs[I], Lows[I], Overflow);
+        Value *Dim = Builder->CreateAdd(Diff, ConstantInt::get(I64, 1), Name + "_dim_size");
+        Total = Overflowing(Intrinsic::umul_with_overflow, Total, Dim, Overflow);
+    }
+    Value *Bytes = Overflowing(Intrinsic::umul_with_overflow, Total, ElementSize, Overflow);
+    RuntimeChecker.emitCheck(Overflow, TooLargeMsg, {RuntimeChecker.lineValue(Line), NameStr});
+    return Bytes;
+}
+
+void ArrayHandler::emitAllocCheck(Value *Ptr, const std::string &Name, int Line) {
+    Value *NameStr = Builder->CreateGlobalString(Name, "array_name", 0, TheModule);
+    Value *TooLargeMsg = Builder->CreateGlobalString(
+        "[Fatal] line %d: Array %s is too large\n", "err_array_large", 0, TheModule);
+    Value *IsNull = Builder->CreateICmpEQ(
+        Ptr, ConstantPointerNull::get(PointerType::getUnqual(*TheContext)), Name + "_alloc_failed");
+    RuntimeChecker.emitCheck(IsNull, TooLargeMsg, {RuntimeChecker.lineValue(Line), NameStr});
+}
+
 const ArrayMetadata &ArrayHandler::defineMetadata(const std::string &Name, const TypeInfo *ElemInfo,
                                                  std::vector<Value*> Lows,
                                                  std::vector<Value*> Highs,
diff --git a/lib/CodeGen/ArrayOutput.cc b/lib/CodeGen/ArrayOutput.cc
index 9306823..99b4a91 100644
--- a/lib/CodeGen/ArrayOutput.cc
+++ b/lib/CodeGen/ArrayOutput.cc
@@ -62,6 +62,8 @@ void ArrayHandler::emitPrintLoop(const std::string &Name,
     }
 
     Function *TheFunction = Builder->GetInsertBlock()->getParent();
+    // Do-while shape: safe because every array has at least one element per
+    // dimension (inverted bounds are rejected at declaration).
     BasicBlock *LoopBB = BasicBlock::Create(*TheContext, "arr_loop", TheFunction);
     BasicBlock *AfterBB = BasicBlock::Create(*TheContext, "arr_after", TheFunction);
 
diff --git a/lib/CodeGen/ArrayParameters.cc b/lib/CodeGen/ArrayParameters.cc
index 57cf6dd..57dc523 100644
--- a/lib/CodeGen/ArrayParameters.cc
+++ b/lib/CodeGen/ArrayParameters.cc
@@ -32,6 +32,7 @@ void ArrayHandler::bindArrayParameter(const std::string &Name,
         Value *TotalBytes = Builder->CreateMul(TotalElements, Meta.ElementSizeC,
                                                Name + "_copy_bytes");
         Value *Copy = Builder->CreateCall(MallocFunc, TotalBytes, Name + "_copy");
+        emitAllocCheck(Copy, Name, CG.DiagnosticLine);
         FunctionType *MemcpyType = FunctionType::get(
             PointerType::getUnqual(*TheContext),
             {PointerType::getUnqual(*TheContext), PointerType::getUnqual(*TheContext),