tree 07e149466ed16b9847a0ad88c3c9fdcd9d03d2cc
parent c87dc10ce3769d5f9edcb5ca40c42d096c576a3a
author Ben Clayton <bclayton@google.com> 1637581497 +0000
committer Tint LUCI CQ <tint-scoped@luci-project-accounts.iam.gserviceaccount.com> 1637581497 +0000

resolver: Add dependency-graph analysis

Performs a module-scope (global) declaration dependency analysis, so
that out-of-order global declarations can be re-ordered into dependency
order for consumption by the resolver.

The WGSL working group are currently debating whether out-of-order
declarations should be included in WebGPU V1, so this implementation
currently errors if module-scope declarations are declared out-of-order,
and the resolver does not currently use this sorted global list.

The analysis does however provide significantly better error diagnostics
when cyclic dependencies are formed, and when globals are declared
out-of-order.

The DependencyGraph also correctly now detects symbol collisions between
functions and types (tint:1308).

With this change, validation is duplicated between the DependencyGraph
and the Resolver. The now-unreachable validation will be removed from
the Resolver with a followup change.

Fixed: tint:1308
Bug: tint:1266
Change-Id: I809c23a069a86cf429f5ec8ef3ad9a98246766ab
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/69381
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Ben Clayton <bclayton@chromium.org>
Reviewed-by: David Neto <dneto@google.com>