交换数组索引 SPARK-Ada 中的潜在别名冲突

Question

Introduction to Spark 课程包含一个示例 (#5)，其中 GNATprove 无法证明在交换数组的两个元素的过程中没有出现别名：

package P
  with SPARK_Mode => On
is
   type P_Array is array (Natural range <>) of Positive;

   procedure Swap_Indexes (A : in out P_Array; I, J : Natural);
   procedure Swap (X, Y : in out Positive);
end P;

package body P
  with SPARK_Mode => On
is
   procedure Swap (X, Y : in out Positive) is
      Tmp : constant Positive := X;
   begin
      X := Y;
      Y := Tmp;
   end Swap;

   procedure Swap_Indexes (A : in out P_Array; I, J : Natural) is
   begin
      Swap (A (I), A (J));
   end Swap_Indexes;

end P;

GNATprove 说 p.adb:13:13: medium: formal parameters "X" and "Y" might be aliased (SPARK RM 6.4.2)。这似乎是一个有效的错误，因为传递给 Swap_Indexes 的索引可能相等。但是，在 Swap_Indexes 中添加前提条件 Pre => I /= J 后，GNATprove 仍然无法证明缺少别名。为什么这个前提条件不充分？

Answer 1

如评论中所述，可以通过从包规范中删除 Swap 子程序来减轻潜在别名的警告。然而，Swap_Indexes 上的先决条件 I /= J 也可以省略，而结果不会改变。此外，再次向包规范中添加一个新的 Swap2 (A, B : in out Positive) 子程序，该子程序仅调用包主体中现在的本地 Swap 将不会导致潜在别名的警告重新出现。这表明问题实际上是对 Swap 的调用，而不是可见性。

查看 GNATprove 的输出（即检查证明的信息），似乎从包规范中删除 Swap 会导致 GNAT 编译器（前端）将 Swap 内联到 Swap_Indexes。内联有效地从 Swap_Indexes 中删除了对 Swap 的调用，并因此有理由警告由于别名造成的潜在影响。

注意：这实际上可以通过将调试选项 -gnatd.j 传递给编译器（参见 here）并将选项 --no-inlining 传递给 GNATprove 来验证如下例所示。

因此，对于特定示例，虽然可以通过从包规范中删除 Swap 来减轻别名警告，但该解决方案并未回答为什么先决条件 I /= J 的原始问题无法证明不存在别名。虽然我不能肯定地说，但我怀疑这只是 GNATprove 证明非静态实际参数不存在别名的能力的当前限制。因此请注意，虽然在示例中的先决条件下不存在混叠效应是显而易见的，但在一般情况下证明这一点可能很快就会变得（非常）困难。

p.ads

package P with SPARK_Mode is

   type P_Array is array (Natural range <>) of Positive;

   procedure Swap_Indexes (A : in out P_Array; I, J : Natural)
     with Pre => I in A'Range and J in A'Range;
   
   procedure Swap2 (A, B : in out Positive)
     with Global => null;
   
end P;

p.adb

package body P with SPARK_Mode is
   
   procedure Swap (X, Y : in out Positive) is
      Tmp : constant Positive := X;
   begin
      X := Y;
      Y := Tmp;
   end Swap_Local;
   
   procedure Swap_Indexes (A : in out P_Array; I, J : Natural) is
   begin
      Swap (A (I), A (J));
   end Swap_Indexes;
   
   procedure Swap2 (A, B : in out Positive) is
   begin
      Swap (A, B);
   end Swap2;

end P;

输出 (GNATprove)

$ gnatprove -Pdefault.gpr -j0 --level=1 --report=all -cargs -gnatd.j
Phase 1 of 2: generation of Global contracts ...
List of calls inlined by the frontend
  1:p.adb:12:7:
  2:p.adb:17:7:
Phase 2 of 2: flow analysis and proof ...
List of calls inlined by the frontend
  1:p.adb:12:7:
  2:p.adb:17:7:
p.adb:4:34: info: index check proved, in call inlined at p.adb:12
p.adb:6:07: info: index check proved, in call inlined at p.adb:12
p.adb:6:12: info: index check proved, in call inlined at p.adb:12
p.adb:7:07: info: index check proved, in call inlined at p.adb:12
p.ads:9:11: info: data dependencies proved
Summary logged in [...]/gnatprove.out

请求 GNATprove 不内联 (--no-inlining) 使警告重新出现，即使先决条件 I /= J 添加到 Swap_Indexes.

输出 (GNATprove)

$ gnatprove --no-inlining -Pdefault.gpr -j0 --level=1 --report=all -cargs -gnatd.j
Phase 1 of 2: generation of Global contracts ...
Phase 2 of 2: flow analysis and proof ...
p.adb:12:13: medium: formal parameters "X" and "Y" might be aliased (SPARK RM 6.4.2)
p.adb:12:16: info: index check proved
p.adb:12:23: info: index check proved
p.ads:9:11: info: data dependencies proved
Summary logged in [...]/gnatprove.out

交换数组索引 SPARK-Ada 中的潜在别名冲突

Potential aliasing violation in swap array indexes SPARK-Ada

formal-verification

formal-methods

ada

spark-ada