GLEP 73：自动执行 REQUIRED_USE 约束

处理算法

现有的包管理器必须在评估依赖关系图时验证 REQUIRED_USE 约束。当前的验证操作被以下算法替换

1. 检查当前用户配置启用的 USE 标志是否满足 REQUIRED_USE 约束。如果是，则接受包（算法停止）。
2. 检查 REQUIRED_USE 约束是否与 REQUIRED_USE 格式的限制 中设置的限制匹配。如果不匹配，则报告 REQUIRED_USE 不匹配并中止。
3. 在 REQUIRED_USE 中查找所有任何一个 (||)、最多一个 (??) 和恰好一个 (^^) 组，并根据下面定义的算法重新排序（排序）。
4. 尝试使用下面定义的算法解决 REQUIRED_USE 约束。如果尝试成功，则接受包并使用求解器确定的 USE 标志集。
5. 如果解决尝试失败，则报告 REQUIRED_USE 不匹配并中止。

REQUIRED_USE 验证算法

验证算法是由 PMS 定义的 REQUIRED_USE 结构的含义隐含的。出于完整性和在进一步算法中重用的目的，此处对其进行了重复。

如果所有顶级项目都计算为真，则认为 REQUIRED_USE 约束满足。根据项目类型，项目计算为真，如果

• 没有以感叹号为前缀的**USE 标志名称**，如果命名的标志已启用，则计算为真。相应地，以感叹号为前缀的 USE 标志名称，如果命名的标志已禁用，则计算为真。
• 对于**使用条件组**，需要首先测试条件（根据相同的规则）。如果条件计算为真，则只有当其中的所有项目都计算为真时，使用条件组才为真。如果条件计算为假，则使用条件组始终计算为真，并且无需测试其中的项目。
• **任何一个组** (||) 如果其中的至少一个项目计算为真，则计算为真。
• **恰好一个组** (^^) 如果其中的恰好一个项目计算为真，并且所有其余项目都计算为假，则计算为真。
• **最多一个组** (??) 如果其中的最多一个项目计算为真，则计算为真。

约束组重新排序算法

约束求解算法建立在所有任何一个、恰好一个和最多一个组的优先左侧假设之上。也就是说，如果当前启用的 USE 标志集不满足约束，则算法优先执行最左侧的约束并禁用最右侧的约束。

由于不同的系统配置文件，可能无法使用 ebuild 指定的最左侧标志自动解决约束（例如，当它被屏蔽时）。为了解决这个问题，规范在求解算法之前提供了一个组重新排序（排序）阶段。

重新排序适用于任何一个、恰好一个和最多一个组。根据格式限制，每个组只能包含扁平的 USE 标志。

对于组中的每个项目，如果该项目命名强制/屏蔽的 USE 标志

• 如果该项目根据标志的值计算为真，则将其移动到组的最左侧位置，
• 如果该项目根据标志的值计算为假，则将其移动到组的最右侧位置，

多个强制/屏蔽标志的相对位置无关紧要，因为这些标志不会更改。

此重新排序确保如果强制使用某个标志，则始终优先于其他选择；如果屏蔽了某个标志，则永远不会优先。这使得能够轻松地处理所有可能的情况，而无需提供详细的算法来处理各种可能的结果。

REQUIRED_USE 求解算法

如果根据配置隐含的 USE 标志的初始集不满足 REQUIRED_USE 约束，则包管理器尝试根据 REQUIRED_USE 更改 USE 标志。

在求解之前，根据强制和屏蔽的 USE 标志确定一组**不可变标志**。如果某个标志被强制或屏蔽，则将其标记为不可变，并且算法不能更改其值。如果特定规则会导致标志被更改，则求解将中止并报告错误。

求解算法至少应用一次，并且在每次应用后重新检查 REQUIRED_USE。包管理器可能支持运行算法的多次迭代，在这种情况下，它需要限制允许的迭代次数或在获得算法先前给出的值之一后中止（遇到无限循环）。

为了强制执行 REQUIRED_USE，需要强制执行 REQUIRED_USE 中未计算为真的每个顶级项目。所有项目都按从左到右的顺序强制执行。根据项目类型，强制执行意味着

• 对于没有以感叹号为前缀的**USE 标志名称**，将启用命名的标志。如果它以感叹号为前缀，则禁用命名的标志。
• 对于**使用条件组**，首先评估条件 (LHS)。如果条件计算为真，则按顺序强制执行组中的所有项目。如果它计算为假，则跳过该组。
• 对于计算为假的**任何一个组**，强制执行该组中的第一个（最左侧）项目。
• 对于计算为假的**最多一个组**，需要首先确定计算为真的第一个（最左侧）项目。之后，强制否定所有后续项目（强制计算为假）。
• **恰好一个组**等效于最多一个组和任何一个组的连接。也就是说，如果所有项目都计算为假，则应用任何一个规则。如果多个项目计算为真，则应用最多一个规则。

否定强制操作只能应用于普通**USE 标志名称**。如果名称没有以感叹号为前缀，则禁用该标志。如果名称以感叹号为前缀，则适当地启用它。

QA 检查的上下文

所有 QA 检查都在特定一组强制和屏蔽的 USE 标志的上下文中执行，称为不可变标志。所有检查都需要针对每个集合重复执行。由于它们可以更改任何一个、最多一个和恰好一个组内的首选项，因此可能还需要针对每个集合执行单独的转换。

可以使用以下算法获得不可变标志组合的完整集合

1. 令U为 REQUIRED_USE 中使用的所有 USE 标志（显式 IUSE 和隐式）的集合，
2. 对于每个启用的配置文件
   1. 令I1为有效的use.force, use.mask, package.use.force, package.use.mask应用于包并影响U中标志的值，
   2. 令I2为有效的use.stable.force, use.stable.mask, package.use.stable.force, package.use.stable.mask应用于包并影响U中标志的值，
   3. 将I1添加到结果集中，
   4. 如果包有任何稳定的关键字，则组合I1和I2，并将结果添加到结果集中。

之后，应针对结果集中所有唯一值执行所有检查。

REQUIRED_USE 约束的要求

为了验证可靠解决 REQUIRED_USE 的能力，QA 检查工具应确保满足以下条件

1. USE 标志的任何有效组合都不能导致约束请求同时启用和禁用相同的标志；
2. USE 标志的任何有效组合（即，不受不可变标志禁止的）都不能尝试更改不可变标志；
3. REQUIRED_USE 中的任何约束都不能以这样一种方式更改标志，即在其之前的任何约束都将开始应用并在第二次迭代中更改结果标志。

将 REQUIRED_USE 转换为蕴涵的概念

用于验证 REQUIRED_USE 的算法依赖于它们以扁平蕴含形式表示。在此形式中，约束表示为零个或多个蕴含。每个蕴含指定零个或多个连接的条件和一个或多个效果。它等效于嵌套的 USE 条件组。如果满足所有条件，则应用效果。

如果约束有效，则其转换的解与原始约束的解相同。

从理念上讲，转换包括以下步骤

1. 根据 约束组重新排序算法 重新排序所有任何一个 (||)、最多一个 (??) 和恰好一个 (^^) 组。
2. 根据以下转换替换所有任何一个 (||)、最多一个 (??) 和恰好一个 (^^) 组
   • ^^ ( a b c… )→|| ( a b c… ) ?? ( a b c… ),
   • || ( a b c… )→!b? ( !c? ( !…? ( a )… ) ),
   • ?? ( a b c… )→a? ( !b !c… ) b? ( !c… ) c? ( … ) ….
3. 创建将所有嵌套条件与其效果链接的有序有向图。
4. 按顺序遍历从最顶层图节点到最深层的路径。

例如，为以下 REQUIRED_USE 约束提供了有序图

a b? ( c? ( d !b ) d? ( e ) ) b? ( f )

节点和边编号以解释排序。此外，最终（效果）节点以红色显示。

遍历此图会按顺序产生以下路径

1. a(1)
2. b(2) → c(3) → d(4)
3. b(2) → c(3) → !b(5)
4. b(2) → d(6) → e(7)
5. b(8) → g(9)

这些路径大致等效于以下 USE 条件组结构

1. a
2. b? ( c? ( d ) )
3. b? ( c? ( !b ) )
4. b? ( d? ( f ) )
5. b? ( g )

除了约束 4 的b的值是从初始值而不是约束 3 可能更改的值考虑的。约束 5 使用单独的条件，因此使用b的新值。

将 REQUIRED_USE 转换为蕴涵的算法

上述转换的步骤 2 到 4 可以使用以下递归函数执行。它应该按顺序应用于每个顶级 REQUIRED_USE 项目。

需要注意的是，为了区分不同的分支，所有条件对象都需要具有唯一的标识。在 Python 中，这可以通过实例化对象自然实现。在其他语言中，可能需要包含显式的唯一标识符。

function transform(item, conditions=[]):
  if item is a USE flag:
    append (conditions, item) to the results
  if item is a USE-conditional group:
    new_conditions := conditions + [item.condition]
    for subitem in item.subitems:
      call transform(subitem, new_conditions)
  if item is an any-of (||) group:
    n := len(item.subitems) - 1  # (last index)
    new_conditions := conditions
    for f in item.subitems[1..n-1]:
      new_conditions += [!f]
    append (new_conditions, item.subitems[0]) to the results
  if item is an at-most-one-of (??) group:
    n := len(item.subitems) - 1  # (last index)
    for i := 0 .. n-1:
      new_conditions := conditions + [item.subitems[i]]
      for f in item.subitems[i+1..n]:
        append (new_conditions, !f) to the results
  if item is an exactly-one-of (^^) group:
    apply the logic for an any-of (||) group
    apply the logic for an at-most-one of (??) group

QA 检查逻辑

参考算法的逻辑被拆分为四个分割函数。

1. 验证约束不会更改不可变标志。
2. 验证约束的条件不相互冲突。
3. 验证没有两个约束会尝试为单个标志强制相反的值。
4. 验证没有任何约束会有效地启用其之前的任何约束。

在下述描述中，C 将表示扁平约束的零个或多个条件（ci 为子条件），E 将表示执行操作。

对不可变标志更改的检查是针对每个约束单独进行的。如果发生以下两个条件，则确定扁平约束会更改不可变标志。

• C 可以计算为真——也就是说，没有一个 ci 指向其值为 ¬ci 的不可变标志。
• E 指向其不可变状态为 ¬E 的不可变标志。

对自冲突约束的检查是针对每个约束单独执行的。如果发生以下条件，则确定扁平约束为自冲突。

• 对于任何一对子条件 ci、cj（i ≠ j），ci = ¬cj。

对尝试为单个标志强制相反值的检查是针对每对约束执行的。由于它是对称的，因此只需要对唯一对执行即可。出于实际原因，让我们假设它对每对 ((Ci, Ei), (Cj, Ej)) 执行，其中 j > i。如果满足以下所有条件，则确定该对会为单个标志强制相反的值。

• Ei = ¬Ej,
• Ci 和 Cj 可以同时计算为真。
• 在应用其之前的所有约束后，Ci 可以计算为真，标志为 F = Ci ∪ Cj。
• 在应用其之前的所有约束后，Cj 可以计算为真，标志为 F = Ci ∪ Cj。

对启用先前约束的检查是针对每对 ((Ci, Ei), (Cj, Ej)) 执行的，其中 j > i。如果满足以下所有条件，则确定约束 (Cj, Ej) 有意义地启用了约束 (Ci, Ei)。

• Ej 与 Ci 中的任何条件匹配（Ej = ci,k，对于任何 k）。
• Ci 和 Cj 可以同时计算为真。
• 在应用所有约束后，Ei 并不总是计算为真，标志为 F = Cj。

如果满足以下条件，则两个扁平约束 Ci 和 Cj 可以同时计算为真。

• 对于每个 ci,k、cj,l（其中 k 和 l 分别是第一和第二约束条件的所有可能索引），ci,k ≠ ¬cj,l。

当且仅当所有子约束都可以计算为真时，约束 C 才能计算为真。如果当前的标志集不包含其否定（对于每个 fj，fj ≠ ci），则子约束 ci 可以计算为真。

当且仅当所有子约束总是计算为真时，约束 C 总是计算为真。如果当前的标志集包含该条件（至少存在一个 fj 使 fj = ci），则子约束 ci 总是计算为真。

为了确定条件 Ci 是否可以在应用特定约束集后计算为真，初始标志为 F1，确定最终标志集 Fn，然后测试约束是否可以在标志 Fn 下计算为真。

为了确定条件 Ci 是否总是在应用特定约束集后计算为真，初始标志为 F1，确定最终标志集 Fn，然后测试约束是否总是在标志 Fn 下计算为真。

为了确定最终标志集 Fn，使用特定约束集 (Ci, Ei) 和初始标志 F1。

• 对于集合中的每个扁平约束 (Ci, Ei)
  • 如果条件 Ci 总是计算为真，则使用 Ei 更新 F（Fi+1 = Fi ∪ {Ei} ∖ {¬Ei}）。

算法的局限性

所提出的检查算法存在一个限制，可能会导致误报。但是，针对 REQUIRED_USE 在 Gentoo 中所有实际用例的测试表明，在撰写此 GLEP 时，没有一个出现过，并且它们不太可能在将来成为主要问题。

该算法无法推断约束的间接含义。例如，给定以下约束

a? ( !b ) !a? ( !b ) b? ( c )

该算法无法正确推断出由于前两个约束，b 将永远不会为真。因此，它将例如在以下情况报告不可变性错误：b? ( c )如果 c 被屏蔽，即使此条件永远不会计算为真。

但是，认为这种约束的自然出现不太可能，并且通常表示约束本身存在问题。因此，在此处报告误报可以作为另一个问题的指示。

嵌套的 any-of、at-most-one-of、exactly-one-of 组

第一个也是最重要的限制是禁止任何一个、最多一个和恰好一个组的嵌套。虽然从技术上讲，此类结构可以工作，但其中一些实际上没有意义，而另一些则非常令人困惑。在撰写本文时，嵌套的 ||/??/^^ 组恰好在两个 Gentoo 软件包中使用。具体用法为

1. app-admin/bacula

   || ( ^^ ( mysql postgres sqlite ) bacula-clientonly )
   

2. dev-games/ogre

   ?? ( gl3plus ( || ( gles2 gles3 ) ) )
   

第一个用法不是很复杂，表示需要选择数据库提供程序中的一个，或者需要使用 bacula-clientonly 标志。但是，乍一看，用户可能会感到困惑，即数据库 ^^ 约束需要独立于 bacula-clientonly 标志应用。可以使用更直接的方式表达相同的结构

!bacula-clientonly? ( ^^ ( mysql postgres sqlite ) )

第二个用法更加令人困惑。这意味着 gl3plus 和 gles2 或 gles3 标志中的任何一个都不能同时启用。但是，gles2 和 gles3 可以同时启用。可以使用更直接的方式表达相同的结构，如下所示：

gl3plus? ( !gles2 !gles3 )

可以看出，在这两种情况下，替代结构都比嵌套表达式更易读且更短。在第一种情况下，这也是表达问题的更自然的方式。虽然替换具有两个以上子表达式的表达式会更难，但到目前为止还没有使用过此类表达式，并且潜在的歧义使它们不太可能出现。

All-of 组

此 GLEP 施加的第二个限制是禁止所有组。PMS 允许它们出现在任何地方，但在现实中，它们仅在 ||、?? 和 ^^ 组内有意义（在其他地方它们没有任何效果，并且可以内联到父块中）。在这些组内，它们暗示只有当所有组内的所有项目都匹配时，才认为该项目匹配。

所有组在 || 内的含义非常清楚。但是，在 ?? 和 ^^ 内可能会发生一些混淆。特别是，对于以下一般情况：

?? ( a ( b c ) )

约束仅影响所有组内所有标志的组合。在这种情况下，启用 a 会禁止同时启用 b 和 c 的组合。但是，可以单独启用 b 或 c 而不会影响 a。这使得此约束不太可能具有实际用例，如果有，它们也不太可能是表达问题的最自然方式。

此外，此类约束的自动求解会强制一些隐式歧义。由于必须同时启用（多个）标志才能使特定项目匹配，因此有多种解决方案可以强制项目不匹配。对于前面提到的示例，启用 a 将需要求解器强制 ( b c ) 不匹配。为此，求解器可以禁用 b、禁用 c 或禁用这两个标志。

这两种选择都有其论点——仅禁用一个标志遵循“所需的最少更改”的理念。禁用两者可以被认为更一致。无论哪种情况，开发人员和用户都会因软件包管理器依赖于任一行为而感到困惑。

|| 内的所有组不会遇到相同的问题，因为求解它们不需要禁用任何内容。但是，它们似乎也价值不高，完全禁止所有组可以提高不同组类型之间的对称性。

此外，嵌套的所有组使转换为蕴涵图变得更加复杂。如果没有它们，条件纯粹是合取的。如果我们要支持 ||、??、^^ 内的所有组，我们将不得不支持析取条件，并将它们转换为合取形式。

在撰写本文时，所有组在 5 个不同的软件包中使用。其中两个位于 ||、??、^^ 之外，使它们毫无意义，可能是偶然的。其余三个案例是

1. sci-chemistry/icm

   ^^ ( ( !32bit 64bit ) ( 32bit !64bit ) ( 32bit 64bit ) )
   

2. media-sound/snd

   ^^ ( ( !ruby !s7 ) ( ruby !s7 ) ( !ruby s7 ) )
   

3. app-i18n/ibus

   || ( deprecated ( gtk3 introspection ) ) )
   

在这些案例中，前两个可以用纯扁平的 || 和 ?? 组适当地替换。此外，它表明 Gentoo 中 ^^ 内所有组的使用纯粹是错误的。

第三个案例可能是有效的。它表示需要启用 deprecated 或 gtk3 和 introspection 两个标志。但是，它没有清楚地表明首选的操作步骤。在调查了相关 ebuild 后，以下约束很可能更正确，并且对用户更清晰

|| ( deprecated gtk3 ) gtk3? ( introspection )

也就是说，如果用户启用了 gtk3 并且 gtk3 需要 introspection，那么启用 introspection 似乎比忽略 gtk3 标志并强制使用 deprecated 模块更合理。

||、??、^^ 组内的 USE 条件

最后一个限制禁止在任何一个、最多一个和恰好一个组内使用 USE 条件组。这些表示该组内的一些项目仅在启用相关标志时才被视为其成员。它们在逻辑上等效于所有组，即|| ( foo? ( bar ) ... )和|| ( ( foo bar ) ... )，但它们具有不同的语义——后一种形式建议启用这两个标志，前一种形式建议仅在已启用 foo 时才考虑 bar。

正确支持 USE 条件组很可能需要针对 USE 条件的不同初始值将父组拆分为多个变体。考虑到上述等式，这与禁止所有组也将不一致。最后，这些组的实际价值很小。

Gentoo 中唯一的用例是在 media-video/mpv 中

opengl? ( || ( aqua egl X raspberry-pi !cli? ( libmpv ) ) )

它表示 OpenGL 视频输出需要选择其中一个变体，并且仅在未启用 CLI 时才允许使用 libmpv 变体。虽然这在技术上可能是有效的，但它令人困惑。此外，其他 REQUIRED_USE 约束已经要求启用 cli 或 libmpv，因此 !cli 意味着 libmpv。因此，约束中的 USE 条件是冗余的。

空的 any-of、at-most-one-of、exactly-one-of 组

正如第一个邮件列表审查所指出的，PMS 明确指定了一个特殊情况，即空任何一个、最多一个和恰好一个组都计算为真。

这种行为被解释为与 Portage 移除任何一个依赖组内不匹配的 USE 条件组相关的历史行为，这可能导致该组实际上变为空。随着 REQUIRED_USE 的引入，该规则有效地扩展到了新的运算符。

尽管如此，目前尚不清楚这在逻辑上是否是正确的方式。Alexis Ballier 指出

> 我的意思是，在我见过的所有情况下，将规则应用于空集 > 就是该规则的中性元素，这样可以保持结合律。 > > 这意味着|| ( )是错误的，&& ( )是正确的，^^ ( )是错误的，>?? ( )是错误的。

（随后的讨论表明，对于?? ( )更正确的结果可能是正确的）

由于原始用例在此处不适用（在这些运算符内部禁止使用 USE 条件组），因此正确行为尚不清楚，并且这没有实际用例，禁止它似乎是最佳做法。

在撰写本文时，此类组没有单一的使用，并且它们自然出现的可能性极小。由于 eclass 生成的字符串，它具有一定的出现可能性，但尚不清楚任何此类情况是否更适合报告为错误。

不同类型约束的应用

该算法旨在以最自然的方式解决不匹配的约束，假设这种解释最可能是正确的。

对于 USE 条件组，它假设它们意味着 *如果 X 为真，则 Y 也应该为真*。适当地，算法不会更改条件中的标志（*X*）；相反，如果条件为真，则它会强制执行组内的表达式（*Y*）。

对于其他组，算法应用自然解释，假设组中的项目按优先级递减的顺序排列，最左边的项目优先级最高。也就是说，如果组计算结果为假，它会强制执行一个解决方案，该解决方案要么禁用除最左边已启用的项目之外的所有已启用项目，要么在没有项目启用时启用第一个项目。

||、??、^^ 组的重新排序

关于组的最左边优先假设导致求解算法依赖于启用项目和禁用其他项目的能力。如果相关标志被屏蔽，或者（在 ??、^^ 的情况下）某些其他标志被强制，则这是不可能的。如果是这种情况，这些组内的排序将必须严格受配置文件之间“公分母”的限制。这有时会导致鼓励不太优选的选项，甚至无法表达约束——例如，如果首选的实现不稳定，但软件包已稳定。

为了解决这个问题，组会被转换以考虑强制/屏蔽（不可变）标志。转换是通过重新排序项目来完成的，因为这使规范尽可能简单。它没有具体说明如何在不同类型的组中解释不可变标志，以及如何处理后续的组。相反，重新排序会导致强制标志自然地被优先考虑，而屏蔽标志自然地被不鼓励。

它还可以自然地处理强制/屏蔽标志导致无法满足约束的情况。这些情况不需要由重新排序算法隐式检测，而是导致求解器尽早失败。

从左到右的约束应用

求解算法按顺序（从左到右）应用所有必要的更改以强制执行约束。强制执行特定顺序，结合 PMS 指定如何组合 ebuild 和 eclass 的 REQUIRED_USE 值，使算法确定性。从左到右应用也是最自然的方式，使开发人员易于预测结果。

最初我曾考虑过使算法独立于约束顺序工作。但是，这将清楚地定义所需的解决方案，并找到一个算法来强制执行该解决方案。为了实现确定性解决方案，我们很可能需要要求开发人员提供不重叠的组。例如

a? ( !b ) b? ( c )

是不可接受的，因为当启用 *a* 和 *b* 标志时，约束将强制执行 *c* 或不强制执行 *c*，具体取决于处理顺序。开发人员必须编写

a? ( !b ) !a? ( !b? ( c ) )

虽然这是一种可能的解决方案，但表达复杂的约束将非常困难。开发人员将不再能够自然地表达约束，而必须为每个请求的结果确定正确的条件集。

单次迭代与多次迭代

本 GLEP 没有特别限制实现执行简单迭代或多次迭代。这两种选择都有其优势。

只要正确排序，单次迭代就可以成功解决所有有效的 REQUIRED_USE 约束。使用单次迭代的实现具有更简单的错误处理——只需要验证强制执行后 REQUIRED_USE 是否实际匹配即可。要求开发人员为单次迭代求解排序其约束也是合理的。

使用多次迭代的优势在于，它们还可以解决排序错误的约束。但是，实现需要考虑无效（循环）约束的可能性，这会导致求解器陷入无限循环。出于这个原因，求解器需要限制最大迭代次数，或者存储以前的结果并检测算法何时再次给出以前的结果之一。

对于大多数现实生活中的用例，两次迭代应该能够解决所有约束。自然编写的 REQUIRED_USE 约束不太可能需要大量迭代。它可能是通过编写诸如以下之类的结构人为造成的

c? ( d ) b? ( c ) a? ( b )

验证的必要性

REQUIRED_USE 约束验证的目的是确保对于所有有效的输入 USE 标志组合，求解器都能够找到有效的解决方案。这需要明确执行，因为复杂的 REQUIRED_USE 约束可能会触发非显而易见的 USE 标志组合的求解问题，导致开发人员错过问题。

由于求解器必须能够处理不可解约束（通过报告它们并让用户处理它们），因此验证对于强制执行 REQUIRED_USE 并不是严格的必要条件。但是，它改善了用户体验，因此是现有 QA 工具中一个有价值的补充。

为了提供最佳覆盖率，将验证集成到开发人员常用的工具（repoman 和 pkgcheck，包括 CI 运行）中是有益的。为了实现这一点，算法必须满足两个要求

• 它必须足够快，以免导致整个存储库的 repoman/pkgcheck 运行时间显着增加。
• 它不得触发大量误报，如果触发了任何误报，则它们应该易于解决。

检查的上下文

如规范部分所述，所有这些检查都需要针对所有可能的不可变标志集重复。这是必要的，因为不可变标志可以显着改变解决方案。特别是

• 它们可以更改任何一个、最多一个和正好一个组中的首选选项，
• 它们可能导致某些约束无法满足，
• 它们可能导致某些 USE 条件组被完全禁用。

为了解决这个问题并避免 REQUIRED_USE 求解在某些配置文件上失败的情况，应针对在启用的配置文件类中找到的所有不可变标志组合执行验证。只需要考虑适用于相关 REQUIRED_USE 约束的标志。

由于 EAPI 5 稳定的屏蔽 [5]，必须分别为 ~arch 和 stable 关键字计算不可变标志。除非软件包实际上是稳定的或正在稳定，否则不需要考虑 stable 变体，以避免不必要地杂乱无章package.use.stable.mask和/或package.use.stable.force对于将保留在 ~arch 中的软件包。

REQUIRED_USE 的要求

对验证强加的规则旨在涵盖大多数常见的不可以解约束情况。特别是

1. 没有有效的 USE 标志组合会导致约束要求同时启用和禁用相同的标志.

   如果有效 REQUIRED_USE 约束（在折叠所有组之后）同时包含 *foo* 和 *!foo*，则验证将永远不会认为约束已满足（因为逻辑上 *x ∧ ¬x* 始终为假）。

2. 没有有效的 USE 标志组合（即不受不可变标志禁止）可以尝试更改不可变标志.

   这是由屏蔽/强制标志的不可变性隐含的。在求解过程中尝试切换这些标志应被视为致命错误，因为use.mask/use.force/… 始终优先于常规配置和包级切换。因此，如果此类标志由 USE 条件组强制执行，则其条件也应相应地屏蔽或强制执行。

3. REQUIRED_USE 中的任何约束都不得以这样的方式更改标志，即在其之前的任何约束都将开始应用并在第二次迭代中更改结果标志.

   这是可靠的单遍求解所必需的。虽然求解可能在多次迭代中正确工作，但可以通过重新排序可靠地（并且通常很容易）修复约束。更重要的是，这还可以捕获由于约束之间的循环切换而无法解决的约束。

已添加第二次迭代更改的附加条件以考虑以下常见情况：a? ( b ) c? ( a b )。虽然从技术上讲，第二条子句导致第一条子句开始应用，但第二条子句已经明确涵盖了这种情况，因此第二次迭代不会改变结果。

转换为蕴涵形式

将 REQUIRED_USE 转换为蕴涵形式用于提供原始约束的一种更方便分析的形式。

首先，所有不同的（便利）项目类型都转换为蕴涵和普通 USE 标志的组合。后者可以准确地表达所有原始约束，前提是在转换之前执行了必要的任何重新排序。因此，我们获得了需要考虑的简化项目集以及与任何一个、最多一个和正好一个组相关联的行为的清晰逻辑映射。

所有转换形式都是根据定义、验证和求解算法构建的

• 如果至少一个项目匹配，则满足任何一个组约束。因此，只有在没有项目匹配时才会应用求解，在这种情况下，第一个项目会被强制执行。适当地，转换的结果是根据所有其他项目的否定强制执行第一个项目（第一个项目的条件被省略，因为它是冗余的——强制执行已启用的标志不会更改任何内容）。
• 如果最多一个项目匹配，则满足最多一个组约束。如果启用了多个项目，则会应用求解，在这种情况下，除了第一个启用的项目之外的所有项目都会被强制禁用。由于禁用已禁用的标志不会更改任何内容，因此可以将其简化为如果匹配最左边的项目则禁用所有剩余项目。转换正是这样做的，对于每个可能启用的项目，从左到右。

• 如果恰好有一个项目匹配，则满足 exactly-one-of 组约束。从逻辑上讲，这等同于至少有一个项目匹配且不超过一个项目匹配。因此，此约束可以转换为 any-of 组和 at-most-one-of 组的组合，其转换已定义。

其次，将项目类型的集合限制为仅两个，其中只有一个可以嵌套，约束可以轻松地转换为图形。生成的图形提供了嵌套条件结构的清晰可视化。除最终（最底层）节点外，所有节点都表示条件，而最终节点表示强制执行。

可以使用普通图形来可视化不同条件和强制执行之间的关系。但是，REQUIRED_USE 处理的细节，特别是从左到右的处理，要求转换保留约束的精确结构。

第三，有了条件的图形（树），我们可以轻松地遍历它们。这样做时，我们构建了精确表达特定强制执行应用需要满足哪些条件的路径。由于约束按顺序应用，因此我们需要按此特定顺序遍历图形，并按相同顺序写下路径。

在执行最后两个步骤时，重要的是我们保留原始条件节点的标识。这对于区分两种情况是必要的

1. a? ( b c )
2. a? ( b ) a? ( c )

由于求解算法递归地应用于 USE 条件组，因此在第一种情况下，外部 a 条件在处理 b 和 c 之间不会重新评估。在后一种情况下，使用单独的组会导致条件重新评估。

虽然在此特定示例中，两种形式之间没有技术差异，但在处理以下极端情况时变得很明显

1. a? ( !a b )
2. a? ( !a ) a? ( b )

在这两种情况下，应用第一个子项都会禁用 a。但是，只有在第二种情况下，求解器才会重新评估 a 的值并省略第二个组。简单的扁平化会导致第一种情况也错误地发生这种情况，从而使转换等效于原始形式。

为了防止这种情况发生，验证算法需要能够确定 a 条件在两个生成的扁平化表达式中是同一个节点，并适当地考虑它不受强制执行的影响。在参考实现中，这是通过保留节点的标识并进行基于标识的节点比较来完成的。

算法的选择

为了验证的目的，考虑了一些算法。

第一个也是最明显的选项是尝试对所有可能的 USE 标志组合强制执行约束，并在任何组合导致失败时报告问题。这种算法具有三个重要的优点

1. 它易于实现并且需要很少的额外代码，
2. 它是可靠的，因为测试了所有 USE 标志的组合——如果任何一个失败，检查将找到它，
3. 它逐字重用验证/强制执行函数，因此检查与基本算法存在分歧的风险很小。

但是，此方法有一个重要的缺点：它很慢。对于每个测试上下文，它都需要处理 2^n 个组合（n——USE 标志的数量）；对于具有 30 个或更多 USE 标志的 REQUIRED_USE 的包（尤其是对于 any-of 组），这个数字可能会变得很大。此外，对于每个组合，检查平均需要 1 到 3 次约束迭代。

可以尝试稍微加快此方法的速度，例如通过将标志分组为单独的、独立的组并分别处理它们。但是，这仍然没有带来明显的收益，并且不是解决问题的可靠方法。因此，这种算法——虽然对测试和参考很有用——不适合与 QA 工具集成。

已经考虑过另一种算法，该算法从左到右处理限制并构建类似决策树的结构以分析 REQUIRED_USE 约束的所有可能结果。但是，此算法的纯版本也被拒绝，因为它无法带来明显的提速——检查仍然需要考虑 2^n 个情况（n——转换后的约束中 USE 条件组的数量）。虽然它肯定比前一个快，特别是它不需要对每个变体进行多次迭代，并且后来的变体需要更少的处理，但它仍然不够快，无法广泛使用。

选择的有效算法在某种程度上是上述方法的简化推导。但是，它不是分析 REQUIRED_USE 约束强制执行的完整决策树，而是专注于分析每个约束的可能影响。指定的算法已拆分为四个逻辑检查，尽管在实际实现中它们可以轻松地组合在一起。两个检查分别对每个扁平化约束执行，另外两个检查对扁平化约束的唯一对执行。结果，有效迭代次数远低于其他情况，每次迭代的复杂度也较低。

即使需要额外的逻辑来防止一些误报，该算法仍然足够快以达到其目的。虽然它并不完美，但它已经在 Gentoo 的所有真实 REQUIRED_USE 案例中进行了测试，并且已验证不会导致任何问题。

验证：更改不可变标志

第一个检查旨在确保在任何情况下，约束都不会尝试切换不可变的标志，即其值通过 use.mask / use.force 文件建立的标志。这个概念不仅对本 GLEP 的范围很重要，而且还确保约束能够得到满足。

通用思想是，以下约束

a? ( b )

与 b 上的 use.mask 结合使用会导致错误，因为如果用户启用 a，则需要 b，但无法启用它。同样，以下

a? ( !b )

使用 b use.forced 将导致错误，因为 b 无法禁用。

如果 a 也被屏蔽，这些约束是可以接受的，以防止条件永远为真。这既是扁平化约束条件规则的原因，也是解决问题的正确方法。

需要注意的是，检查是针对每个扁平化约束单独进行的，并且不考虑其他约束的影响。也就是说，给定以下示例约束

!a? ( !b ) b? ( c )

如果 a 和 c 都被屏蔽，检查仍然会认为 REQUIRED_USE 错误，即使 b 永远不可能为真。但是，这在现实中并不被认为是一个问题，可以通过屏蔽 b 来解决。它还将提高 USE 标志的清晰度，并避免产生 b 可以启用的错误印象。

验证：自相矛盾的约束

此检查并不特别重要；它主要作为先决条件检查添加，以避免向后续检查提供意外输入。它旨在捕获自相矛盾的条件，例如

a? ( !a? ( b ) )

可以清楚地看到，此条件永远不会评估为真，因为它需要 a 同时启用和禁用。

这种约束的出现极不可能。但是，它实际上破坏了算法的一些假设，因为它不可能提供满足条件的有效标志集。因此，它被明确拒绝为无效。

验证：强制标志取相反的值

此检查旨在解决两个不同约束的组合需要标志同时启用和禁用这种情况。一个通用的例子是

a? ( c )
b? ( !c )

在这里，第一个约束需要启用 c，而第二个约束需要禁用它。因此，如果用户同时启用 a 和 b，则无法满足约束。此处唯一明确允许的强制执行是按顺序启用和禁用 c，这两者都不能解决问题。

算法中列出的第一个条件验证了问题最重要的症状——两个扁平化约束需要标志的不同值。其余条件旨在排除误报。

第二个规则指出，这两个条件需要能够同时评估为真，或者换句话说，这两个条件不能包含相反的值。例如，这排除了以下情况

a? ( c )
!a? ( b? ( !c ) )

在这种情况下，两个条件永远无法同时评估为真，因为它们需要 a 的相反值。

第三和第四规则旨在验证在考虑所有在其之前的约束后，条件是否可以实际发生。这旨在避免以下类型的误报

!a? ( !b )
!a? ( !c )
b? ( c )

在这里，在考虑前两个条件后，第二个和第三个约束可以同时发生，因为 !a 和 b 彼此不冲突。但是，在考虑在其之前的约束后，很明显它们不能同时发生，因为 !a 会隐式禁用 b，从而使第三个条件为假。

需要注意的是，这也适用于以下极端情况

c? ( a )
a? ( b )
d? ( !a )
!a? ( !b )

因为即使算法会错误地假设第二个和第四个条件不能同时发生，它也会检测到第一个和第三个条件之间的冲突。

验证：启用约束之前的条件

此检查验证约束不会有意义地导致在其之前的约束开始应用。这实际上意味着需要多次迭代算法才能强制执行它们的约束。

一个通用的例子是

b? ( c )
a? ( b )

在这种情况下，仅启用 a 将导致在第一次迭代中启用 b，在第二次迭代中启用 c。

第一个条件验证了问题最重要的症状——即后面约束的影响与前面约束的条件匹配。其余条件排除了误报。

同样，第二个条件检查这两个条件是否可以同时发生，也就是说，它们之间不冲突。此规则排除的一个误报通用示例是

!a? ( b? ( c ) )
a? ( b )

在这种情况下，尽管第二个约束强制执行 b（这是第一个约束的条件之一），但这两个条件不能同时发生，因为 a 必须同时启用和禁用。

第三条规则检查后面约束的条件是否无论如何都不会强制执行与前面约束相同的效果。也就是说，它们解释了相对常见的模式

b? ( c )
a? ( b )
a? ( c )

即使第二个约束导致第一个约束开始应用，启用 a 也会导致第三个约束应用。由于第三个约束与第一个约束具有相同的效果，因此应用第一个约束将没有效果（约束将已经满足），并且不需要第二次迭代。

辅助算法

规范还提供了辅助算法来确定两种情况：条件何时可以评估为真，以及条件何时始终评估为真。一般来说，算法只关注**强**强制执行，即那些保证会发生的强制执行。

因此，假设一个条件可以评估为真，除非至少有一个子条件不能评估为真。也就是说，如果条件的形式为

a? ( b? ( c? ( ... ) ) )

则假设它可以评估为真，除非我们在当前强制执行的标志状态中显式地拥有!a、!b和/或!c。否则，我们假设标志可以具有任何值，因此可以通过适当的标志值使条件为真。

相应地，一个条件始终评估为真，只有当我们知道所有子条件都将评估为真时。在前面提到的示例中，这意味着当前标志必须显式列出a、b和c。否则，我们假设其中一个标志可以具有相反的值，因此使条件评估为假。

在确定有效标志时，我们只关注条件始终评估为真（使用处理约束时的标志值）的扁平化约束。这样做是为了避免强制执行在实际用例中可能不会强制执行的任何标志。考虑到以上情况，这意味着此类约束将强制执行的标志处于未定义状态，并且不限制后续的约束。

如限制部分所述，此逻辑存在一个限制，即它无法推断约束的复杂含义，例如

!a? ( b ) a? ( b )

如果在处理时a的值未定义，则算法将假定没有一个条件保证为真，因此b将保持未定义状态。但是，这被认为是不太可能发生的极端情况，并且不是主要问题。

此 GLEP 中不允许的约束

为了简化，此 GLEP 将拒绝一些根据 PMS 有效的 REQUIRED_USE 形式。对于不满足约束的所有 USE 标志组合，都将拒绝它们。但是，由于三个原因，这不是一个主要问题

1. 不受支持的约束极其罕见，价值低，修复它们可以提高可读性。如基本原理 允许的 REQUIRED_USE 语法限制 中所列，在撰写本文时，共有 8 个包受到影响，并且正在修复它们。
2. 约束仅被拒绝用于自动解决，但仍支持 REQUIRED_USE 验证。因此，包管理器只会将无法解决的 REQUIRED_USE 报告给用户，这不会造成与之前状态的回归。
3. 此 GLEP 并不严格禁止包管理器解决这些约束，只是没有为它们指定解决方案。因此，包管理器可以实现自定义扩展来解决它们。但是，它们仍然应该警告说这是不可移植且不可读的。

无法求解的约束

并非所有有效的 REQUIRED_USE 约束都可以可靠地解决。这有两个主要原因

1. 切换标志的约束，这些标志导致先前的条件不适用。解决这些问题可能需要多次迭代解决算法。但是，通常可以通过重新排序轻松地修复它们。
2. 标志之间存在冲突的约束。解决这些问题将导致约束不满足的重复结果。使用多迭代解决，它们会导致无限循环。它们没有简单的解决方案。

但是，问题通常仅适用于某些不允许的 USE 标志组合。验证算法应该能够检测到大多数此类情况。

具有次优解的约束

虽然此规范使用一种尝试以最自然的方式读取 REQUIRED_USE 约束的算法，但并非 Gentoo 中的所有约束都以这种方式编写。特别是，许多 any-of、at-most-one-of 和 exactly-one-of 组是在没有特定顺序的情况下编写的。在某些情况下，它们与 USE 条件组互换使用。一些 USE 条件组是在不考虑清楚建立条件与组内项目之间关系的情况下编写的。

虽然自动解决算法能够解决许多此类约束，但解决方案可以被认为是次优的，因为它们没有遵循开发人员会明知故犯地建议的解决方案。例如，根据当前规则，以下两个约束等效

feature? ( dep )
!dep? ( !feature )

但是，根据自动解决语义，第一个将优先启用依赖项，而第二个将优先禁用功能。

这可能是最重要的问题，因为没有简单的方法可以自动检测到它。