Skip to content

non-deterministic resolving of packages leads to build failures #13662

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
matu3ba opened this issue Nov 26, 2022 · 3 comments · Fixed by #13670
Closed

non-deterministic resolving of packages leads to build failures #13662

matu3ba opened this issue Nov 26, 2022 · 3 comments · Fixed by #13670
Labels
bug Observed behavior contradicts documented or intended behavior frontend Tokenization, parsing, AstGen, Sema, and Liveness.
Milestone

Comments

@matu3ba
Copy link
Contributor

matu3ba commented Nov 26, 2022

Zig Version

0.11.0-dev.333+d5e41bf15b

Steps to Reproduce and Observed Behavior

git clone https://github.com/matu3ba/ZigCacheIssue
cd ZigCacheIssue/Intermittent_Success/major/
/usr/bin/time -v

Executing takes ca. 90 seconds to have an almost certain chance to reproduce the issue:

(ins)[user@pc major]$ /usr/bin/time -v ./b.sh 
STEP 1
STEP 2
STEP 3
STEP 4
STEP 5
STEP 6
STEP 7
STEP 8
STEP 9
STEP 10
succ_cnt: 4, fail_cnt: 6
cwd: /home/misterspoon/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major
succ_cnt: 4, fail_cnt: 6
        Command being timed: "./b.sh"
        User time (seconds): 79.38
        System time (seconds): 2.90
        Percent of CPU this job got: 101%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 1:20.97
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 309948
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 468
        Minor (reclaiming a frame) page faults: 1250658
        Voluntary context switches: 39595
        Involuntary context switches: 2513
        Swaps: 0
        File system inputs: 0
        File system outputs: 227744
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0

The sporadic failure appearing is

/home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/major.zig:1:27: error: no package named 'minor' available within package 'root'
pub const minor = @import("minor");
                          ^~~~~~~
referenced by:
    Foo: /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/major.zig:2:17
    Foo: /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/src/alpha.zig:7:18
    remaining reference traces hidden; use '-freference-trace' to see all reference traces

error: test...
error: The following command exited with error code 1:
/home/user/dev/git/zi/zig/master/build/stage3/bin/zig test /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/main_test.zig --cache-dir /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/zig-cache --global-cache-dir /home/user/.cache/zig --name test --pkg-begin major /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/major.zig --pkg-begin minor /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/minor/minor.zig --pkg-end --pkg-en d --enable-cache 
error: the following build command failed with exit code 1:
/home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/zig-cache/o/552a17303a3cfe25f45a59a25ba92fda/build /home/user/dev/git/zi/zig/master/build/stage3/bin/zig /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major /home/user/dev/git/zi/ZigCacheIssue_MinExample/Intermittent_Success/major/zig-cache /home/user/.cache/zig test

Dependencies are resolved in the following way for the project in directory Intermittent_Success:

ma/build                             ┌────┐
pkg ma (ma/ma), mi(mi/mi)            │    ▼
ma/main_test ┬► ma/src/alpha ─► ma/ma│┬► Foo = mi/mi.Foo ─► mi/mi.Foo = mi/src/foo.Foo ─► mi/src/foo: pub fn Foo
             │                       │└► beta = src/beta.beta
             │                       └─────┐             │
             │                             │             │
             │                             │             ▼
             └► ma/src/beta ─► Foo = ma/ma.Foo, pub fn beta
                                ▲                        │using Foo internally
                                └────────────────────────┘

For more details, look at https://github.com/matu3ba/ZigCacheIssue.

Expected Behavior

Failure to compile in all cases or successful compilation.

Note, that we still have a directed acyclic graph(DAG) of the package usage, so the resolving logic is definitely broken:
Only the file major.zig in package major includes the package minor by including file minor.zig with Foo.

What could be a bigger problem is when package usage does not form an DAG and there should be a way to check this somehow.

Also note, that only writing this up takes very long and big thanks to @BlueAlmost for providing the rough reduction.

@matu3ba matu3ba added the bug Observed behavior contradicts documented or intended behavior label Nov 26, 2022
@mlugg
Copy link
Member

mlugg commented Nov 27, 2022

I need to look at the project structure more closely to confirm, but skimming through the details, this seems like a case of an issue I identified where the compiler will currently trip up on any case where a single file is imported from multiple packages, since it basically gets analysed as part of the package of whichever file AstGen reached first. It was probably hard to reduce this further since it's a race condition so changes which don't "resolve" the issue might nevertheless randomly stop it happening. I spoke to Andrew about this on Discord a while back, and we agreed it makes sense to try and enforce that every file is a part of exactly one package. It turns out a good implementation of this (with consistent errors) is surprisingly irritating, but I do have some local work on it which I'll try and get back to soon.

@mlugg
Copy link
Member

mlugg commented Nov 27, 2022

Okay yeah, that is indeed what's going on. The package minor is included in both root and major:

  • root imports beta.zig imports major.zig imports minor
  • major is major.zig imports minor

So if AstGen happens to hit the first part first (it's a race condition because AstGen is run on a thread pool), you get the error (since it's assumed that major.zig is "owned" by root, so it tries to resolve the import of minor in that context), otherwise compilation succeeds.

@matu3ba
Copy link
Contributor Author

matu3ba commented Nov 27, 2022

I need more time to investigate more details on this. I looked at this yesterday with @mikdusan for 1-2 hours or so.

hard to reduce this further since it's a race condition so changes

It was tricky, but @mikdusan managed to get 100% failure rate with the following patch:

diff --git a/Intermittent_Success/major/src/alpha.zig b/Intermittent_Success/major/src/alpha.zig
index 034e191..504143c 100644
--- a/Intermittent_Success/major/src/alpha.zig
+++ b/Intermittent_Success/major/src/alpha.zig
@@ -1,5 +1,5 @@
 const std = @import("std");
-pub const major = @import("major");
+//pub const major = @import("major");
 
 test "alpha foo" {
     const result = true;

One can have faster iteration time (without external script, without nuking cache, without build.zig providided by @mikdusan ) with zig test main_test.zig --pkg-begin major major.zig --pkg-begin minor ../minor/minor.zig --pkg-end --pkg-end, once one uses 21bd13626d66c36c327bb317bd09cad979d92327 (d24aaf8847336e12b6571e13d57f6d112452d97d regressed behavior, not sure if its only from cli).

He also found out that zig test main_test.zig --pkg-begin minor ../minor/minor.zig --pkg-end works repeatedly.

Unfortunately the logs dont contain the full relative path from cwd, but one can see with zig test --debug-log module main_test.zig --pkg-begin major major.zig --pkg-begin minor ../minor/minor.zig --pkg-end --pkg-end that these files are found not to be cached before emitting the error:

// a pile of stuff
debug(module): File.getSource, not cached. pkgdir=. sub_file_path=major.zig
debug(module): File.getSource, not cached. pkgdir=. sub_file_path=src/beta.zig
// the error

mlugg added a commit to mlugg/zig that referenced this issue Nov 27, 2022
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
mlugg added a commit to mlugg/zig that referenced this issue Nov 27, 2022
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
@Vexu Vexu added the frontend Tokenization, parsing, AstGen, Sema, and Liveness. label Dec 5, 2022
@Vexu Vexu added this to the 0.10.1 milestone Dec 5, 2022
mlugg added a commit to mlugg/zig that referenced this issue Dec 7, 2022
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
mlugg added a commit to mlugg/zig that referenced this issue Dec 25, 2022
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
@andrewrk andrewrk modified the milestones: 0.10.1, 0.11.0 Jan 10, 2023
mlugg added a commit to mlugg/zig that referenced this issue Jan 22, 2023
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
mlugg added a commit to mlugg/zig that referenced this issue Jan 22, 2023
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
mlugg added a commit to mlugg/zig that referenced this issue Jan 22, 2023
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
mlugg added a commit to mlugg/zig that referenced this issue Jan 22, 2023
Previously, if a source file was referenced from multiple packages, it
just became owned by the first one AstGen happened to reach; this was a
problem, because it could lead to inconsistent behaviour in the compiler
based on a race condition. This could be fixed by just analyzing such
files multiple times - however, it was pointed out by Andrew that it
might make more sense to enforce files being part of at most a single
package. Having a file in multiple packages would not only impact
compile times (due to Sema having to run multiple times on potentially a
lot of code) but is also a confusing anti-pattern which more often than
not is a mistake on the part of the user.

Resolves: ziglang#13662
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Observed behavior contradicts documented or intended behavior frontend Tokenization, parsing, AstGen, Sema, and Liveness.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants