Closed llogick closed 1 month ago
The new std.ComptimeStrigMap
uses the following calculation. That should work
The new
std.ComptimeStrigMap
uses the following calculation. That should work
That's already in play
zig env
{
"zig_exe": "/home/rad/lab/zig/build/stage4/bin/zig",
"lib_dir": "/home/rad/lab/zig/build/stage4/lib/zig",
"std_dir": "/home/rad/lab/zig/build/stage4/lib/zig/std",
"global_cache_dir": "/home/rad/.cache/zig",
"version": "0.14.0-dev.1248+7bbbbf8ff",
...}
cat /home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig | grep 'pub inline fn initComptime' -A15
pub inline fn initComptime(comptime kvs_list: anytype) Self {
comptime {
var self = Self{};
if (kvs_list.len == 0)
return self;
// Since the KVs are sorted, a linearly-growing bound will never
// be sufficient for extreme cases. So we grow proportional to
// N*log2(N).
@setEvalBranchQuota(10 * kvs_list.len * std.math.log2_int_ceil(usize, kvs_list.len));
var sorted_keys: [kvs_list.len][]const u8 = undefined;
var sorted_vals: [kvs_list.len]V = undefined;
self.initSortedKVs(kvs_list, &sorted_keys, &sorted_vals);
const final_keys = sorted_keys;
git blame says 4months ago, here's why they are insufficient https://github.com/ziglang/zig/pull/21135#issuecomment-2295950537
cc @travisstaloch
Those values end up being way too low
git diff
diff --git a/src/parser.zig b/src/parser.zig
index f85f9b3..f17ece0 100644
--- a/src/parser.zig
+++ b/src/parser.zig
@@ -22,6 +22,8 @@ pub fn staticStringMapInitComptime(comptime T: type, comptime kvs_list: anytype)
@setEvalBranchQuota(kvs_list.len * kvs_list.len);
return std.ComptimeStringMap(T, kvs_list);
} else {
+ @compileLog(10 * kvs_list.len * std.math.log2_int_ceil(usize, kvs_list.len));
+ @setEvalBranchQuota(10 * kvs_list.len * std.math.log2_int_ceil(usize, kvs_list.len));
return std.StaticStringMap(T).initComptime(kvs_list);
}
}
~/lab/zta/misc/zig-lsp-codegen main !1
❯ zig build test
test
└─ run test parser
└─ zig test test parser Debug native 1 errors
src/parser.zig:25:9: error: found compile log statement
@compileLog(10 * kvs_list.len * std.math.log2_int_ceil(usize, kvs_list.len));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/parser.zig:25:9: note: also here (2 times)
Compile Log Output:
@as(usize, 60)
@as(usize, 80)
@as(usize, 20)
error: the following command failed with 1 compilation errors:
/home/rad/lab/zig/build/stage4/bin/zig test -ODebug -Mroot=/home/rad/lab/zta/misc/zig-lsp-codegen/src/parser.zig --cache-dir /home/rad/lab/zta/misc/zig-lsp-codegen/.zig-cache --global-cache-dir /home/rad/.cache/zig --name test parser --zig-lib-dir /home/rad/lab/zig/build/stage4/lib/zig/ --listen=-
test
└─ run test
└─ zig test Debug native 6 errors
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:1291:5: error: evaluation exceeded 1000 backwards branches
for (slice[start_index..], start_index..) |c, i| {
^~~
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:1291:5: note: use @setEvalBranchQuota() to raise the branch limit from 1000
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:1275:25: note: called from here
return indexOfAnyPos(T, slice, 0, values);
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/SemanticVersion.zig:87:43: note: called from here
const extra_index = std.mem.indexOfAny(u8, text, "-+");
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
src/parser.zig:11:76: note: called from here
const static_string_map_renamed_zig_version = std.SemanticVersion.parse("0.13.0-dev.33+8af59d1f9") catch unreachable;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lsp.zig:1639:33: note: called from here
) parser.StaticStringMap(ParamsParserFunc(Params, Source)) {
~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lsp.zig:1607:47: note: called from here
} else if (methodToParamsParserMap(Notification.Params, @TypeOf(params_source)).get(method)) |parse| {
~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:1291:5: error: evaluation exceeded 1000 backwards branches
for (slice[start_index..], start_index..) |c, i| {
^~~
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:1291:5: note: use @setEvalBranchQuota() to raise the branch limit from 1000
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:1275:25: note: called from here
return indexOfAnyPos(T, slice, 0, values);
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/SemanticVersion.zig:87:43: note: called from here
const extra_index = std.mem.indexOfAny(u8, text, "-+");
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
src/parser.zig:11:76: note: called from here
const static_string_map_renamed_zig_version = std.SemanticVersion.parse("0.13.0-dev.33+8af59d1f9") catch unreachable;
~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lsp.zig:1639:33: note: called from here
) parser.StaticStringMap(ParamsParserFunc(Params, Source)) {
~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/lsp.zig:1321:48: note: called from here
if (methodToParamsParserMap(Notification.Params, std.json.Value).get(item.method)) |parse| {
~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:150:29: error: evaluation exceeded 1300 backwards branches
std.mem.swap([]const u8, &ctx.keys[a], &ctx.keys[b]);
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:150:29: note: use @setEvalBranchQuota() to raise the branch limit from 1300
/home/rad/lab/zig/build/stage4/lib/zig/std/sort.zig:49:25: note: called from here
context.swap(j, j - 1);
~~~~~~~~~~~~^~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/sort/pdq.zig:65:44: note: called from here
break sort.insertionContext(range.a, range.b, context);
~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:595:24: note: called from here
std.sort.pdqContext(a, b, context);
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:167:36: note: called from here
mem.sortUnstableContext(0, sorted_keys.len, SortContext{
~~~~~~~~~~~~~~~~~~~~~~~^
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:85:35: note: called from here
self.initSortedKVs(kvs_list, &sorted_keys, &sorted_vals);
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/parser.zig:27:51: note: called from here
return std.StaticStringMap(T).initComptime(kvs_list);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
src/lsp.zig:2512:50: note: called from here
break :blk parser.staticStringMapInitComptime(void, kvs_list);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:150:29: error: evaluation exceeded 1150 backwards branches
std.mem.swap([]const u8, &ctx.keys[a], &ctx.keys[b]);
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:150:29: note: use @setEvalBranchQuota() to raise the branch limit from 1150
/home/rad/lab/zig/build/stage4/lib/zig/std/sort.zig:49:25: note: called from here
context.swap(j, j - 1);
~~~~~~~~~~~~^~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/sort/pdq.zig:65:44: note: called from here
break sort.insertionContext(range.a, range.b, context);
~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:595:24: note: called from here
std.sort.pdqContext(a, b, context);
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:167:36: note: called from here
mem.sortUnstableContext(0, sorted_keys.len, SortContext{
~~~~~~~~~~~~~~~~~~~~~~~^
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:85:35: note: called from here
self.initSortedKVs(kvs_list, &sorted_keys, &sorted_vals);
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/parser.zig:27:51: note: called from here
return std.StaticStringMap(T).initComptime(kvs_list);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
src/parser.zig:151:85: note: called from here
const enum_from_string_map: StaticStringMap(T) = staticStringMapInitComptime(T, kvs);
~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:151:29: error: evaluation exceeded 1000 backwards branches
std.mem.swap(V, &ctx.vals[a], &ctx.vals[b]);
~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:151:29: note: use @setEvalBranchQuota() to raise the branch limit from 1000
/home/rad/lab/zig/build/stage4/lib/zig/std/sort.zig:49:25: note: called from here
context.swap(j, j - 1);
~~~~~~~~~~~~^~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/sort/pdq.zig:65:44: note: called from here
break sort.insertionContext(range.a, range.b, context);
~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/mem.zig:595:24: note: called from here
std.sort.pdqContext(a, b, context);
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:167:36: note: called from here
mem.sortUnstableContext(0, sorted_keys.len, SortContext{
~~~~~~~~~~~~~~~~~~~~~~~^
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:85:35: note: called from here
self.initSortedKVs(kvs_list, &sorted_keys, &sorted_vals);
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
src/parser.zig:27:51: note: called from here
return std.StaticStringMap(T).initComptime(kvs_list);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
src/parser.zig:151:85: note: called from here
const enum_from_string_map: StaticStringMap(T) = staticStringMapInitComptime(T, kvs);
~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:178:17: error: evaluation exceeded 1000 backwards branches
while (len > self.kvs.keys[i].len) {
^~~~~
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:178:17: note: use @setEvalBranchQuota() to raise the branch limit from 1000
/home/rad/lab/zig/build/stage4/lib/zig/std/static_string_map.zig:95:36: note: called from here
self.initLenIndexes(&len_indexes);
~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
src/parser.zig:27:51: note: called from here
return std.StaticStringMap(T).initComptime(kvs_list);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
src/parser.zig:151:85: note: called from here
const enum_from_string_map: StaticStringMap(T) = staticStringMapInitComptime(T, kvs);
~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
Compile Log Output:
@as(usize, 60)
@as(usize, 60)
@as(usize, 1300)
@as(usize, 4690)
@as(usize, 1150)
@as(usize, 400)
@as(usize, 20)
@as(usize, 60)
@as(usize, 150)
@as(usize, 60)
@as(usize, 360)
@as(usize, 60)
@as(usize, 20)
@as(usize, 60)
@as(usize, 20)
@as(usize, 60)
@as(usize, 80)
@as(usize, 0)
error: the following command failed with 6 compilation errors:
/home/rad/lab/zig/build/stage4/bin/zig test -ODebug --dep parser --dep types -Mroot=/home/rad/lab/zta/misc/zig-lsp-codegen/src/lsp.zig -Mparser=/home/rad/lab/zta/misc/zig-lsp-codegen/src/parser.zig --dep parser -Mtypes=/home/rad/lab/zta/misc/zig-lsp-codegen/.zig-cache/o/36a9869865821ea850ea079026a50694/lsp_types.zig --cache-dir /home/rad/lab/zta/misc/zig-lsp-codegen/.zig-cache --global-cache-dir /home/rad/.cache/zig --name test --zig-lib-dir /home/rad/lab/zig/build/stage4/lib/zig/ --listen=-
Build Summary: 2/7 steps succeeded; 2 failed
test transitive failure
├─ run test transitive failure
│ └─ zig test Debug native 6 errors
└─ run test parser transitive failure
└─ zig test test parser Debug native 1 errors
Cheers
Thats surprising. Maybe a adversarial (reverse sorted by length) input? Perhaps StaticStringMap.initComptime() needs to bump its limit a little after those recent changes to how @setEvalBranchQuota works. :thinking:
fixed by 193a210ebe4a090a6f1bf1cb538375b56472688d
zig version 0.14.0-dev.1248+7bbbbf8ff
Tests pass with
2000
, ZLS needs3000
, not sure what a decent dynamic value would be.