)]}'
{
  "commit": "ed2a73266f1d9a0aeeebc3e1e07045848a62254e",
  "tree": "3b113d950d4bc8dd072979111af9414cba36159b",
  "parents": [
    "62fab8aefdd0d5dafb5d9f6a2e3a86e953deffc5"
  ],
  "author": {
    "name": "David \u0027Digit\u0027 Turner",
    "email": "digit@google.com",
    "time": "Sun Jun 07 23:21:18 2026 +0200"
  },
  "committer": {
    "name": "gn-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "email": "gn-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Thu Jun 25 05:36:07 2026 -0700"
  },
  "message": "Change resolution algorithm to reduce edge walks\n\nThis CL changes how state changes are propagated during\nresolution. It reduces the number of notifications\nfrom dependencies to dependents, but ensuring that\neach record is resolved and finalized as soon as possible\nbefore notifying its dependents.\n\nFor example, let\u0027s consider a simple A -\u003e B -\u003e C\ndependency chain, where:\n\n- A is defined and waiting for B to resolve.\n- B is defined and waiting for C to resolve.\n- C is not defined yet (loader still evaluating its BUILD.gn file).\n\nOnce the new C item definition arrives, before this\nCL, the following events would happen:\n\n- C is defined (can resolve)\n  C is resolved (can finalize)\n  C notifies B\n    B is resolved (cannot finalize)\n    B notifies A\n      A waits (cannot resolve)\n    B waits (cannot finalize)\n  C finalizes    -\u003e writes C\n  C notifies B\n    B finalizes  -\u003e writes B\n    B notifies A\n      A finalizes  -\u003e writes A\n\nWith this CL, this becomes shorter and writes\nare performed earlier:\n\n- C is defined\n  C is resolved\n  C is finalized   -\u003e writes C\n  C notifies B\n    B is resolved\n    B is finalized  -\u003e writes B\n    B notifies A\n      A is resolved\n      A is finalized -\u003e writes A\n\nThe conditions blocking state changes are not modified,\nonly the notifications are delayed, preserving the\ncorrectness of the algorithm. However, this will change\nthe order of writes when validations are used, because\ntheir dependents can be finalized before them, consider\nthe following:\n\n  A --validation--\u003e B ---\u003e C\n\nBefore this CL (when C is not defined yet), A was finalized\n(written) before B\n\n- C is defined + resolved\n  C notifies B\n    B is resolved\n    B notifies A\n      A resolves\n      A finalizes  --\u003e writes A\n    B waits (cannot finalize)\n  C finalizes    --\u003e writes C\n  C notifies B\n    B finalizes   --\u003e writes B\n\nAfter this CL, A is finalized after B:\n\n- C is defined\n  C is resolved\n  C is finalized --\u003e writes C\n  C notifies B\n    B resolves + finalizes --\u003e writes B\n    B notifies A\n      A finalizes --\u003e writes A\n\nSince B is a validation dependency in the Ninja build plan, this doesn\u0027t\nchange its overall graph, only the order in which the corresponding\nbuild statements are defined.\n\nBenchmarking shows a slight benefit in `gn gen` time\n(-2% on a medium Fuchsia graph)\n\n+ Change debug log message to use \u0027dependent --\u003e dependency\u0027 instead\n  of \u0027dependency --\u003e dependent\u0027 for clarity.\n\n+ Minor type change for ItemType and RecordState (char -\u003e unsigned char)\n  to avoid any potential platform-specific signess issues.\n\nChange-Id: I6a5d19e251e5ca982cd6a64f21bdc96efbf62fc8\nReviewed-on: https://gn-review.googlesource.com/c/gn/+/23141\nReviewed-by: Takuto Ikuta \u003ctikuta@google.com\u003e\nCommit-Queue: David Turner \u003cdigit@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "cc4d6ffd8b78aeb800947a2059dc2dfc5ccc14d5",
      "old_mode": 33188,
      "old_path": "src/gn/builder.cc",
      "new_id": "aca80d72732e07fdc5911a180e7752c9af515ea6",
      "new_mode": 33188,
      "new_path": "src/gn/builder.cc"
    },
    {
      "type": "modify",
      "old_id": "5e6c88a58a7efc8abf74e329a1f659235aea547c",
      "old_mode": 33188,
      "old_path": "src/gn/builder.h",
      "new_id": "542b75107f4436b40dcdc6d71425d726f6caaa24",
      "new_mode": 33188,
      "new_path": "src/gn/builder.h"
    },
    {
      "type": "modify",
      "old_id": "8896925a605c4c18e29082dc55577ce4f1db3447",
      "old_mode": 33188,
      "old_path": "src/gn/builder_record.cc",
      "new_id": "6feb3af8ed92a8cfcce2fd4671498dc594054b49",
      "new_mode": 33188,
      "new_path": "src/gn/builder_record.cc"
    },
    {
      "type": "modify",
      "old_id": "fd05fd8d16fd60ce47b6a6faad78c3d6286e0049",
      "old_mode": 33188,
      "old_path": "src/gn/builder_record.h",
      "new_id": "52d4816123bb037b9bd53d2618e494d8fd5a29ab",
      "new_mode": 33188,
      "new_path": "src/gn/builder_record.h"
    },
    {
      "type": "modify",
      "old_id": "8e08fab08f0908607e10a91dbd7518c9267b6397",
      "old_mode": 33188,
      "old_path": "src/gn/builder_unittest.cc",
      "new_id": "54d9f5e48470707cc0c67074b2356ecbfd739deb",
      "new_mode": 33188,
      "new_path": "src/gn/builder_unittest.cc"
    }
  ]
}