| // Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import 'space.dart'; |
| import 'static_type.dart'; |
| |
| /// Calculates whether the intersection of [left] and [right] is empty. |
| /// |
| /// This is used to tell if two field spaces on a pair of spaces being |
| /// subtracted have no common values. |
| bool intersectEmpty(Space left, Space right) { |
| // The intersection with an empty space is always empty. |
| if (left == Space.empty) return true; |
| if (right == Space.empty) return true; |
| |
| // The intersection of a union is empty if all of the arms are. |
| if (left is UnionSpace) { |
| return left.arms.every((arm) => intersectEmpty(arm, right)); |
| } |
| |
| if (right is UnionSpace) { |
| return right.arms.every((arm) => intersectEmpty(left, arm)); |
| } |
| |
| // Otherwise, we're intersecting two [ExtractSpaces]. |
| return _intersectExtracts(left as ExtractSpace, right as ExtractSpace); |
| } |
| |
| /// Returns true if the intersection of two static types [left] and [right] is |
| /// empty. |
| bool intersectTypes(StaticType left, StaticType right) { |
| // If one type is a subtype, the subtype is the intersection. |
| if (left.isSubtypeOf(right)) return false; |
| if (right.isSubtypeOf(left)) return false; |
| |
| // Unrelated types. |
| return true; |
| } |
| |
| /// Returns the interaction of extract spaces [left] and [right]. |
| bool _intersectExtracts(ExtractSpace left, ExtractSpace right) { |
| if (intersectTypes(left.type, right.type)) return true; |
| |
| // Recursively intersect the fields. |
| List<String> fieldNames = |
| {...left.fields.keys, ...right.fields.keys}.toList(); |
| for (String name in fieldNames) { |
| // If the fields are disjoint, then the entire space will have no values. |
| if (_intersectFields(left.fields[name], right.fields[name])) return true; |
| } |
| |
| return false; |
| } |
| |
| bool _intersectFields(Space? left, Space? right) { |
| if (left == null) return right! == Space.empty; |
| if (right == null) return left == Space.empty; |
| return intersectEmpty(left, right); |
| } |