tree 3b113d950d4bc8dd072979111af9414cba36159b
parent 62fab8aefdd0d5dafb5d9f6a2e3a86e953deffc5
author David 'Digit' Turner <digit@google.com> 1780867278 +0200
committer gn-scoped@luci-project-accounts.iam.gserviceaccount.com <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1782390967 -0700

Change resolution algorithm to reduce edge walks

This CL changes how state changes are propagated during
resolution. It reduces the number of notifications
from dependencies to dependents, but ensuring that
each record is resolved and finalized as soon as possible
before notifying its dependents.

For example, let's consider a simple A -> B -> C
dependency chain, where:

- A is defined and waiting for B to resolve.
- B is defined and waiting for C to resolve.
- C is not defined yet (loader still evaluating its BUILD.gn file).

Once the new C item definition arrives, before this
CL, the following events would happen:

- C is defined (can resolve)
  C is resolved (can finalize)
  C notifies B
    B is resolved (cannot finalize)
    B notifies A
      A waits (cannot resolve)
    B waits (cannot finalize)
  C finalizes    -> writes C
  C notifies B
    B finalizes  -> writes B
    B notifies A
      A finalizes  -> writes A

With this CL, this becomes shorter and writes
are performed earlier:

- C is defined
  C is resolved
  C is finalized   -> writes C
  C notifies B
    B is resolved
    B is finalized  -> writes B
    B notifies A
      A is resolved
      A is finalized -> writes A

The conditions blocking state changes are not modified,
only the notifications are delayed, preserving the
correctness of the algorithm. However, this will change
the order of writes when validations are used, because
their dependents can be finalized before them, consider
the following:

  A --validation--> B ---> C

Before this CL (when C is not defined yet), A was finalized
(written) before B

- C is defined + resolved
  C notifies B
    B is resolved
    B notifies A
      A resolves
      A finalizes  --> writes A
    B waits (cannot finalize)
  C finalizes    --> writes C
  C notifies B
    B finalizes   --> writes B

After this CL, A is finalized after B:

- C is defined
  C is resolved
  C is finalized --> writes C
  C notifies B
    B resolves + finalizes --> writes B
    B notifies A
      A finalizes --> writes A

Since B is a validation dependency in the Ninja build plan, this doesn't
change its overall graph, only the order in which the corresponding
build statements are defined.

Benchmarking shows a slight benefit in `gn gen` time
(-2% on a medium Fuchsia graph)

+ Change debug log message to use 'dependent --> dependency' instead
  of 'dependency --> dependent' for clarity.

+ Minor type change for ItemType and RecordState (char -> unsigned char)
  to avoid any potential platform-specific signess issues.

Change-Id: I6a5d19e251e5ca982cd6a64f21bdc96efbf62fc8
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/23141
Reviewed-by: Takuto Ikuta <tikuta@google.com>
Commit-Queue: David Turner <digit@google.com>