The attempt of what I was trying to do here was fairly basic.
You have a string. In the string you can replace values enclosed with {..} according to some definition.
E.g. some can be replaced by values in an enum, others are replaced with a counting numeric value, others a fixed string. Now, since I wanted to support more than one variable length strings, I had to introduce the concept of scopes. In this way, the restriction is lightened. As opposed to one variable length string per string, it’s at most one variable length string per scope since we can determine the max length of the variable length string from the other fields in the scope.
Selecting the values for {..} will output a filled out string.
The torture starts with the counting values and the enums. For those, you will have multiple instances of the string. E.g. if your enum is ‘A’, ‘B’, ‘C’, and someone selects A & B, you want to generate two instances of your string, one with ‘A’ and one with ‘B’. say you have two enums in the string, this one with ‘X’ and ‘Y’, then you’ll want all combinations of (‘A’, ‘X’), (‘A’, ‘Y’), (‘B’, ‘X’), (‘B’, ‘Y’), (‘C’, ‘X’), (‘C’, ‘Y’).
So, from this we can see the problem is “simply” forming the Cartesian products of all these sets. Then for each n-uple in the Cartesian product fill out the format string.
Now, actually doing that is a pain in the ass. So, for selecting from the enums, I thought to use an array of u1 (0 = unset, 1 = set. Array of u1 instead of u32 bitset due to ease of use). This minimizes the memory used for selecting each enum.
Per the topic’s original premise, I wanted to minimize the number of allocs. So, that array of u1 is a single call to alloc where the length is the sum of all enums. E.g. in the aformentioned example alloc(u1, 2 + 3).
Filling it out is a non-issue as the filling out is iterative. E.g. you handle ‘A’, ‘B’, ‘C’ first, so, once that’s done, you know you’re working on array[3..], and once you handle ‘X’, ‘Y’ you know you’re at array[5..].
It’s the Cartesian product aspect that dooms me.
My only thought is to also alloc a counter to know which value in each enum I’m currently writing out during this iteration of writing out the filled out string.
The proceeding is from a new day: so, I thought to try incrementing in order. E.g., is there a rule to the mod of each field that I can increment each value each iteration and have it work out? Ultimately, I couldn’t get that to work, so I “flipped” how I viewed the problem and just did it the traditional way of fixing [0-n] counters and updating the n + 1 counter (which, if it rolls over, means updating counter n, etc.)
So, I finally have this working (save for variable strings).
const std = @import("std");
const Capture = struct {
section: usize,
start: usize,
end: usize,
};
const Section = struct {
parent_idx: usize,
exclusive_length: u8,
};
fn parseSections(format: [] const u8, sections: []Section, captures: []Capture) !void {
var section_idx: usize = 0;
var furthest_idx: usize = 0;
var capture: bool = false;
sections[0].parent_idx = 0;
sections[0].exclusive_length = 0;
var num_captures: usize = 0;
for (format, 0..) |c, idx| {
switch (c) {
'(' => {
furthest_idx += 1;
sections[furthest_idx].parent_idx = section_idx;
sections[furthest_idx].exclusive_length = 0;
section_idx = furthest_idx;
},
')' => {
section_idx = sections[section_idx].parent_idx;
},
'{' => {
if (capture) {
return error.InvalidExpression;
}
else {
captures[num_captures].section = section_idx;
captures[num_captures].start = idx + 1;
num_captures += 1;
capture = true;
}
},
'}' => {
if (!capture) {
return error.InvalidExpression;
} else if (captures[num_captures - 1].section != section_idx) {
return error.InvalidExpression;
} else {
captures[num_captures - 1].end = idx;
capture = false;
}
},
else => {
if (capture) {
} else {
sections[section_idx].exclusive_length += 1;
}
},
}
}
}
const DefinitionType = enum {
enumerable,
countable,
var_string,
};
const FullDefinition = struct {
name: []const u8,
definition: Definition,
};
const Definition = union (DefinitionType) {
enumerable: EnumDefinition,
countable: CountDefinition,
var_string: VarStringDefinition,
};
const EnumDefinition = struct {
values: []const []const u8,
};
const CountDefinition = struct {
};
const VarStringDefinition = struct {
};
const DefBinding = struct {
capture_idx: usize,
definition_idx: usize,
};
fn processCountable(value: *usize, reader: *std.Io.Reader, writer: *std.Io.Writer) !void {
try writer.print("Set max value:\n", .{});
try writer.flush();
const line = try reader.takeDelimiterExclusive('\n');
reader.toss(1);
value.* = try std.fmt.parseUnsigned(u32, line, 10);
std.debug.print("Selection: {d}\n", .{value.*});
}
fn processEnum(selected: []u1, definition: EnumDefinition, reader: *std.Io.Reader, writer: *std.Io.Writer) !void {
try writer.print("Select from:\n", .{});
for (definition.values) |value| {
try writer.print("{s}\n", .{value});
}
try writer.flush();
const line = try reader.takeDelimiterInclusive('\n');
var last_start: usize = 0;
for (line, 0..) |c, idx| {
if (c == ',' or c == '\n') {
const selection = line[last_start..idx];
std.debug.print("Selection: {s}\n", .{selection});
const found_idx: ?usize = for (definition.values, 0..) |value, value_idx| {
if (std.mem.eql(u8, value, selection)) {
break value_idx;
}
} else null;
if (found_idx) |value| {
selected[value] = 1;
} else {
return error.InvalidSelection;
}
last_start = idx + 1;
}
}
}
fn updateCounters(counters: []usize, max_values: []usize) void {
var i: usize = counters.len;
while (i > 0): (i -= 1) {
const idx = i - 1;
counters[idx] += 1;
if (counters[idx] == max_values[idx]) {
counters[idx] %= max_values[idx];
} else {
return;
}
}
}
pub fn main() !void {
const site_values = [_][]const u8{
"us",
"jp",
};
const site_enum_def = EnumDefinition{
.values = &site_values,
};
const environment_values = [_][]const u8{
"dev",
"prod",
};
const environment_enum_def = EnumDefinition{
.values = &environment_values,
};
const server_count_def = CountDefinition{};
const definitions: [3]FullDefinition = .{
.{
.name = "site",
.definition = .{ .enumerable = site_enum_def },
},
.{
.name = "environment",
.definition = .{ .enumerable = environment_enum_def },
},
.{
.name = "count",
.definition = .{ .countable = server_count_def },
},
};
const format = "{site}|{environment}|{count}";
var section_count: usize = 1; // implicit outermost section
var capture_count: usize = 0;
for (format) |c| {
switch (c) {
'{' => {
capture_count += 1;
},
'(' => {
section_count += 1;
},
else => {
}
}
}
const GPA = std.heap.GeneralPurposeAllocator(.{});
var gpa: GPA = .init;
var allocator = gpa.allocator();
const sections = try allocator.alloc(Section, section_count);
defer allocator.free(sections);
const captures = try allocator.alloc(Capture, capture_count);
defer allocator.free(captures);
const bindings = try allocator.alloc(DefBinding, capture_count);
defer allocator.free(bindings);
try parseSections(format, sections, captures);
outer: for (captures, 0..) |capture, capture_idx| {
for (definitions, 0..) |full_definition, def_idx| {
if (std.mem.eql(u8, format[capture.start..capture.end], full_definition.name)) {
bindings[capture_idx].capture_idx = capture_idx;
bindings[capture_idx].definition_idx = def_idx;
continue: outer;
}
}
return error.DefinitionNotFound;
}
var num_enums: usize = 0;
var num_countables: usize = 0;
var enum_size: usize = 0;
{
var i: usize = 0;
const len: usize = bindings.len - 1;
while (i <= len): (i += 1) {
const forward_idx = len - i;
const binding = bindings[forward_idx];
const capture = captures[binding.capture_idx]; // technically same as forward idx.
const full_definition = definitions[binding.definition_idx];
std.debug.print("{s}\n", .{format[capture.start..capture.end]});
switch (full_definition.definition) {
.enumerable => |enum_def| {
num_enums += 1;
enum_size += enum_def.values.len;
},
.countable => |count_def| {
_ = count_def;
num_countables += 1;
},
.var_string => {
},
}
}
}
const enum_flag_array = try allocator.alloc(u1, enum_size);
defer allocator.free(enum_flag_array);
@memset(enum_flag_array, 0);
const countable_value_array = try allocator.alloc(usize, num_countables);
defer allocator.free(countable_value_array);
const max_capture_values = try allocator.alloc(usize, capture_count);
defer allocator.free(max_capture_values);
var stdin_buffer: [1024]u8 = undefined;
var stdin = std.fs.File.stdin().reader(&stdin_buffer);
var stdout_buffer: [1024]u8 = undefined;
var stdout = std.fs.File.stdout().writer(&stdout_buffer);
var max_combinations: usize = 1;
{
var enum_start: usize = 0;
var countable_start: usize = 0;
var i: usize = 0;
const len: usize = bindings.len - 1;
while (i <= len): (i += 1) {
const forward_idx = len - i;
const binding = bindings[forward_idx];
const capture = captures[binding.capture_idx]; // technically same as forward idx.
const full_definition = definitions[binding.definition_idx];
sw: switch (full_definition.definition) {
.enumerable => |enum_def| {
const selected = enum_flag_array[enum_start..(enum_start + enum_def.values.len)];
processEnum(
selected,
enum_def,
&stdin.interface,
&stdout.interface
) catch |err| switch (err) {
error.InvalidSelection => {
continue :sw full_definition.definition;
},
else => {
continue :sw full_definition.definition;
},
};
var num_selected:usize = 0;
for (selected) |value| {
if (value == 1) {
num_selected += 1;
}
}
max_capture_values[binding.capture_idx] = num_selected;
max_combinations *= num_selected;
enum_start += enum_def.values.len;
std.debug.print("Enum values: ", .{});
for (enum_def.values) |value| {
std.debug.print("{s}\n", .{value});
}
},
.countable => |count_def| {
_ = count_def;
try processCountable(
&countable_value_array[countable_start],
&stdin.interface,
&stdout.interface,
);
max_combinations *= countable_value_array[countable_start];
max_capture_values[binding.capture_idx] = countable_value_array[countable_start];
countable_start += 1;
},
.var_string => {
max_capture_values[binding.capture_idx] = 1;
},
}
}
}
const capture_counters = try allocator.alloc(usize, capture_count);
@memset(capture_counters, 0);
var current_combination: usize = 0;
while (current_combination < max_combinations): (current_combination += 1) {
var current_capture: usize = 0;
var enum_start: usize = 0;
var i: usize = 0;
while (i < format.len): (i += 1) {
const c = format[i];
switch (c) {
'{' => {
const binding = bindings[current_capture];
const full_definition = definitions[binding.definition_idx];
switch (full_definition.definition) {
.enumerable => |enum_def| {
const enum_set = enum_flag_array[enum_flag_array.len - (enum_start + enum_def.values.len)..(enum_flag_array.len - enum_start)];
enum_start += enum_def.values.len;
const active_selected = capture_counters[current_capture];
var current_position: usize = 0;
for (enum_set, 0..) |value, idx| {
if (value == 1) {
if (current_position == active_selected) {
std.debug.print("{s}", .{enum_def.values[idx]});
break;
}
current_position += 1;
}
} else {
unreachable; // at least one is always selected.
}
},
.countable => {
const value = capture_counters[current_capture];
std.debug.print("{d}", .{value});
},
else => {},
}
current_capture += 1;
i = captures[binding.capture_idx].end;
},
'}' => {
},
'(' => {},
')' => {},
else => {
std.debug.print("{c}", .{c});
},
}
}
updateCounters(capture_counters, max_capture_values);
}
}