tiny.accy.choir.shape

1pub const Expression = struct {2    constant: i64 = 0,3    terms: []const Term = &.{},45    pub fn eql(self: Expression, other: Expression) bool {6        if (self.constant != other.constant or self.terms.len != other.terms.len) return false;7        for (self.terms, other.terms) |lhs, rhs| {8            if (lhs.symbol != rhs.symbol or lhs.coefficient != rhs.coefficient) return false;9        }10        return true;11    }1213    pub fn isConstant(self: Expression) bool {14        return self.terms.len == 0;15    }1617    pub fn staticValue(self: Expression) ?u64 {18        if (!self.isConstant() or self.constant < 0) return null;19        return @intCast(self.constant);20    }21};

1pub const Term = struct {2    symbol: SymbolId,3    coefficient: i64 = 1,4};

1pub const Bounds = struct {2    min: ?u64 = null,3    opt: ?u64 = null,4    max: ?u64 = null,56    pub fn valid(self: Bounds) bool {7        if (self.min == null and self.opt == null and self.max == null) return false;8        if (self.min) |min| {9            if (self.opt) |opt| {10                if (min > opt) return false;11            }12            if (self.max) |max| {13                if (min > max) return false;14            }15        }16        if (self.opt) |opt| {17            if (self.max) |max| {18                if (opt > max) return false;19            }20        }21        return true;22    }23};

1pub const Fact = struct {2    mode: Mode,3    predicate: Predicate,4};

1pub const Mode = enum {2    assume,3    assert,4};

1pub const Predicate = union(enum) {2    equal: Equality,3    bound: Bound,4    divisible: Divisibility,5};

1pub const Builder = struct {2    backing_allocator: std.mem.Allocator,3    arena_state: *alloc_arena.Arena,4    name: []const u8,5    symbols: std.ArrayListUnmanaged(Symbol) = .empty,6    tensors: std.ArrayListUnmanaged(tensor_mod.Tensor) = .empty,7    facts: std.ArrayListUnmanaged(fact_mod.Fact) = .empty,89    pub fn init(backing_allocator: std.mem.Allocator, name: []const u8) !Builder {10        if (name.len == 0) return Error.EmptyName;11        const arena_state = try backing_allocator.create(alloc_arena.Arena);12        errdefer backing_allocator.destroy(arena_state);13        arena_state.* = alloc_arena.Arena.init(backing_allocator);14        errdefer arena_state.deinit();15        const alloc = arena_state.allocator();16        return .{17            .backing_allocator = backing_allocator,18            .arena_state = arena_state,19            .name = try alloc.dupe(u8, name),20        };21    }2223    pub fn deinit(self: *Builder) void {24        self.arena_state.deinit();25        self.backing_allocator.destroy(self.arena_state);26        self.* = undefined;27    }2829    pub fn symbol(self: *Builder, name: []const u8) !expression.SymbolId {30        if (name.len == 0) return Error.EmptyName;31        if (self.findSymbol(name) != null) return Error.DuplicateSymbol;32        const alloc = self.arena();33        const id: expression.SymbolId = @intCast(self.symbols.items.len);34        try self.symbols.append(alloc, .{ .name = try alloc.dupe(u8, name) });35        return id;36    }3738    pub fn symbolExpression(self: *Builder, id: expression.SymbolId) !expression.Expression {39        try self.requireSymbol(id);40        const terms = try self.arena().alloc(expression.Term, 1);41        terms[0] = .{ .symbol = id };42        return .{ .terms = terms };43    }4445    pub fn scaledSymbolExpression(self: *Builder, id: expression.SymbolId, coefficient: i64, constant: i64) !expression.Expression {46        try self.requireSymbol(id);47        const terms = try self.arena().alloc(expression.Term, 1);48        terms[0] = .{ .symbol = id, .coefficient = coefficient };49        return .{ .constant = constant, .terms = terms };50    }5152    pub fn constantExpression(_: *Builder, value: i64) expression.Expression {53        return expression.constant(value);54    }5556    pub fn addExpression(self: *Builder, lhs: expression.Expression, rhs: expression.Expression) !expression.Expression {57        try self.requireExpression(lhs);58        try self.requireExpression(rhs);59        const terms = try self.arena().alloc(expression.Term, lhs.terms.len + rhs.terms.len);60        @memcpy(terms[0..lhs.terms.len], lhs.terms);61        @memcpy(terms[lhs.terms.len..], rhs.terms);62        return .{ .constant = lhs.constant + rhs.constant, .terms = terms };63    }6465    pub fn tensor(self: *Builder, name: []const u8, extents: []const expression.Expression) !usize {66        if (name.len == 0) return Error.EmptyName;67        if (self.findTensor(name) != null) return Error.DuplicateTensor;68        const alloc = self.arena();69        const id = self.tensors.items.len;70        const owned_extents = try alloc.alloc(expression.Expression, extents.len);71        for (extents, owned_extents) |extent, *owned_extent| owned_extent.* = try self.ownTensorExtent(extent);72        try self.tensors.append(alloc, .{73            .name = try alloc.dupe(u8, name),74            .extents = owned_extents,75        });76        return id;77    }7879    pub fn assumeEqual(self: *Builder, lhs: expression.Expression, rhs: expression.Expression) !void {80        try self.appendFact(.assume, .{ .equal = .{ .lhs = lhs, .rhs = rhs } });81    }8283    pub fn assertEqual(self: *Builder, lhs: expression.Expression, rhs: expression.Expression) !void {84        try self.appendFact(.assert, .{ .equal = .{ .lhs = lhs, .rhs = rhs } });85    }8687    pub fn assumeBounds(self: *Builder, value: expression.Expression, bounds: fact_mod.Bounds) !void {88        try self.appendBounds(.assume, value, bounds);89    }9091    pub fn assertBounds(self: *Builder, value: expression.Expression, bounds: fact_mod.Bounds) !void {92        try self.appendBounds(.assert, value, bounds);93    }9495    pub fn assumeDivisible(self: *Builder, value: expression.Expression, divisor: u64) !void {96        try self.appendDivisible(.assume, value, divisor);97    }9899    pub fn assertDivisible(self: *Builder, value: expression.Expression, divisor: u64) !void {100        try self.appendDivisible(.assert, value, divisor);101    }102103    pub fn finish(self: *Builder) Family {104        const result = Family{105            .backing_allocator = self.backing_allocator,106            .arena_state = self.arena_state,107            .name = self.name,108            .symbols = self.symbols.items,109            .tensors = self.tensors.items,110            .facts = self.facts.items,111        };112        self.* = undefined;113        return result;114    }115116    fn appendBounds(self: *Builder, mode: fact_mod.Mode, value: expression.Expression, bounds: fact_mod.Bounds) !void {117        if (!bounds.valid()) return Error.InvalidBounds;118        try self.appendFact(mode, .{ .bound = .{ .value = value, .bounds = bounds } });119    }120121    fn appendDivisible(self: *Builder, mode: fact_mod.Mode, value: expression.Expression, divisor: u64) !void {122        if (divisor == 0) return Error.InvalidDivisor;123        try self.appendFact(mode, .{ .divisible = .{ .value = value, .divisor = divisor } });124    }125126    fn appendFact(self: *Builder, mode: fact_mod.Mode, predicate: fact_mod.Predicate) !void {127        const owned_predicate = try self.ownPredicate(predicate);128        try self.facts.append(self.arena(), .{ .mode = mode, .predicate = owned_predicate });129    }130131    fn arena(self: *Builder) std.mem.Allocator {132        return self.arena_state.allocator();133    }134135    fn findSymbol(self: *const Builder, name: []const u8) ?expression.SymbolId {136        for (self.symbols.items, 0..) |item, index| {137            if (std.mem.eql(u8, item.name, name)) return @intCast(index);138        }139        return null;140    }141142    fn findTensor(self: *const Builder, name: []const u8) ?usize {143        for (self.tensors.items, 0..) |item, index| {144            if (std.mem.eql(u8, item.name, name)) return index;145        }146        return null;147    }148149    fn requireSymbol(self: *const Builder, id: expression.SymbolId) !void {150        if (id >= self.symbols.items.len) return Error.UnknownSymbol;151    }152153    fn requireExpression(self: *const Builder, value: expression.Expression) !void {154        for (value.terms) |term| try self.requireSymbol(term.symbol);155    }156157    fn ownTensorExtent(self: *Builder, value: expression.Expression) !expression.Expression {158        const owned = try self.ownExpression(value);159        if (owned.terms.len == 0 and owned.constant < 0) return Error.InvalidExtent;160        return owned;161    }162163    fn ownExpression(self: *Builder, value: expression.Expression) !expression.Expression {164        try self.requireExpression(value);165        if (value.terms.len == 0) return .{ .constant = value.constant };166        return .{167            .constant = value.constant,168            .terms = try self.arena().dupe(expression.Term, value.terms),169        };170    }171172    fn ownPredicate(self: *Builder, predicate: fact_mod.Predicate) !fact_mod.Predicate {173        switch (predicate) {174            .equal => |value| return .{ .equal = .{175                .lhs = try self.ownExpression(value.lhs),176                .rhs = try self.ownExpression(value.rhs),177            } },178            .bound => |value| return .{ .bound = .{179                .value = try self.ownExpression(value.value),180                .bounds = value.bounds,181            } },182            .divisible => |value| return .{ .divisible = .{183                .value = try self.ownExpression(value.value),184                .divisor = value.divisor,185            } },186        }187    }188};

1pub const Error = error{2    DuplicateSymbol,3    DuplicateTensor,4    EmptyName,5    InvalidBounds,6    InvalidDivisor,7    InvalidExtent,8    UnknownSymbol,9};

1pub const Family = struct {2    backing_allocator: std.mem.Allocator,3    arena_state: *alloc_arena.Arena,4    name: []const u8,5    symbols: []const Symbol,6    tensors: []const tensor_mod.Tensor,7    facts: []const fact_mod.Fact,89    pub fn deinit(self: *Family) void {10        self.arena_state.deinit();11        self.backing_allocator.destroy(self.arena_state);12        self.* = undefined;13    }1415    pub fn symbolIndex(self: Family, name: []const u8) ?expression.SymbolId {16        for (self.symbols, 0..) |item, index| {17            if (std.mem.eql(u8, item.name, name)) return @intCast(index);18        }19        return null;20    }2122    pub fn tensor(self: Family, name: []const u8) ?tensor_mod.Tensor {23        for (self.tensors) |item| {24            if (std.mem.eql(u8, item.name, name)) return item;25        }26        return null;27    }2829    pub fn assumedFactCount(self: Family) usize {30        var count: usize = 0;31        for (self.facts) |item| {32            if (item.mode == .assume) count += 1;33        }34        return count;35    }3637    pub fn assertedFactCount(self: Family) usize {38        var count: usize = 0;39        for (self.facts) |item| {40            if (item.mode == .assert) count += 1;41        }42        return count;43    }44};

1pub const Symbol = struct {2    name: []const u8,3};

1pub const Tensor = struct {2    name: []const u8,3    extents: []const expression.Expression,45    pub fn rank(self: Tensor) usize {6        return self.extents.len;7    }8};

1pub const SymbolId = u32;

1pub fn constant(value: i64) Expression {2    return .{ .constant = value };3}

1pub fn family(value: family_mod.Family) choir.product.incremental.Fingerprint {2    var builder = choir.product.incremental.FingerprintBuilder{};3    builder.updateBytes("accy.choir.shape.family");4    builder.updateBytes(value.name);5    builder.updateUsize(value.symbols.len);6    for (value.symbols) |symbol| builder.updateBytes(symbol.name);7    builder.updateUsize(value.tensors.len);8    for (value.tensors) |tensor_value| hashTensor(&builder, tensor_value);9    builder.updateUsize(value.facts.len);10    for (value.facts) |fact_value| hashFact(&builder, fact_value);11    return builder.finish();12}

1pub const shape = @import("shape/root.zig");

1const expression = @import("expression.zig");2const fact = @import("fact.zig");3const family = @import("family.zig");4const fingerprint_mod = @import("fingerprint.zig");5const tensor = @import("tensor.zig");67pub const SymbolId = expression.SymbolId;8pub const Term = expression.Term;9pub const Expression = expression.Expression;10pub const Bounds = fact.Bounds;11pub const Predicate = fact.Predicate;12pub const Fact = fact.Fact;13pub const FactMode = fact.Mode;14pub const Tensor = tensor.Tensor;15pub const Symbol = family.Symbol;16pub const Family = family.Family;17pub const Builder = family.Builder;18pub const Error = family.Error;19pub const constant = expression.constant;20pub const fingerprint = fingerprint_mod.family;