commit f2b26ad501c38ee9abbf27d217490d82b6ab9b6e
author nharmata <nharmata@google.com> Wed Mar 06 09:37:00 2019 -0800
committer Copybara-Service <copybara-worker@google.com> Wed Mar 06 09:39:18 2019 -0800
tree 7b432c4a79e2785d302e1523bc3cb5f1d235af1e
parent 9525a60e16c194f2210e638c3a66de8f9b0efd3e

Refactor "determine all dependency edges from all aspects" logic to be a streaming visitation.

In doing so, we use more efficient algorithm that notably doesn't have several large sources of garbage. The inefficiencies and garbage churn of the old algorithm are more easily noticed when you consider the pseudo-code.

The old algorithm for was:

  res <- []
  for each attribute A of T that entails a label dep
    for each label dep L entailed by A
      aspectDeps <- {}
      for each aspect S of A
        if S is satisfied by T
          for each attribute A' of S
            for each label dep L' entailed by A'
              // Note that L' has nothing directly to do with L.
              aspectDeps <- aspectDeps U {A', L')
      for each {a, l} in aspectDeps
        res <- res + [l]
  return res

And the new algorithm is:

  res <- []
  for each attribute A of T that entails a label dep
    for each aspect S of A
      if there exists a label dep L entailed by A that satisfies S
        for each label dep L' entailed by S
          res <- res + [L']
  return res

This refactor exposes an existing inefficiency in LabelVisitor. I added a TODO comment explaining it.

RELNOTES: None
PiperOrigin-RevId: 237063485