shape/case_enum/all.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
use crate::case_enum::deduplicate_shape::extend_or_insert_shape;
use crate::location::Location;
use crate::{Shape, ShapeCase};
use indexmap::{IndexMap, IndexSet};
/// The inner type of [`ShapeCase::All`] which intentionally can't be constructed directly because
/// it requires simplifying the inner shapes to achieve the desired result.
///
/// Construct this via [`Shape::all`].
#[derive(Clone, Debug, Eq)]
pub struct All {
shapes: Vec<Shape>,
}
impl All {
pub fn iter(&self) -> impl Iterator<Item = &Shape> {
self.shapes.iter()
}
}
impl<'a> IntoIterator for &'a All {
type Item = &'a Shape;
type IntoIter = std::slice::Iter<'a, Shape>;
fn into_iter(self) -> Self::IntoIter {
self.shapes.iter()
}
}
impl PartialEq<All> for All {
fn eq(&self, other: &All) -> bool {
self.shapes.iter().collect::<IndexSet<_>>() == other.shapes.iter().collect::<IndexSet<_>>()
}
}
/// Builds a [`Shape`] with [`ShapeCase::All`] _unless_ the shapes can simplify to a single
/// [`ShapeCase`].
#[allow(clippy::too_many_lines)]
pub(crate) fn all(shapes: impl Iterator<Item = Shape>, mut locations: Vec<Location>) -> Shape {
let mut flat_shapes = Vec::new();
for shape in shapes {
if let ShapeCase::All(inner_shapes) = shape.case() {
locations.extend(shape.locations.clone());
for inner_shape in inner_shapes {
extend_or_insert_shape(&mut flat_shapes, inner_shape.clone());
}
} else {
extend_or_insert_shape(&mut flat_shapes, shape);
}
}
// Store arrays and objects separately so we can merge them
let mut arrays_to_merge = Vec::new();
let mut objects_to_merge = Vec::new();
flat_shapes.retain(|shape| match shape.case() {
ShapeCase::Array { prefix, tail } => {
// Store arrays separately so we can merge them into one array
arrays_to_merge.push((prefix.clone(), tail.clone(), shape.locations.clone()));
false
}
ShapeCase::Object { fields, rest } => {
// Store object fields separately so we can merge them into one object
objects_to_merge.push((fields.clone(), rest.clone(), shape.locations.clone()));
false
}
_ => true,
});
// The presence of the null literal shape (ShapeCase::Null)
// in flat_shapes subsumes all the other shapes.
if let Some(null_shape) = flat_shapes
.iter()
.find(|shape| shape.case() == ShapeCase::Null)
{
return null_shape.clone();
}
// The presence of any specific Bool literal shapes subsumes
// the general Bool shape.
if flat_shapes
.iter()
.any(|shape| matches!(shape.case.as_ref(), ShapeCase::Bool(Some(_))))
{
flat_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Bool(None)));
}
if flat_shapes
.iter()
.any(|shape| matches!(shape.case.as_ref(), ShapeCase::Int(Some(_))))
{
// The presence of any specific Int literal shapes subsumes
// the general Int shape and the general Float shape.
flat_shapes.retain(|shape| {
!matches!(shape.case.as_ref(), ShapeCase::Float | ShapeCase::Int(None))
});
} else if flat_shapes
.iter()
.any(|shape| shape.case() == ShapeCase::Int(None))
{
// The presence of the general Int shape subsumes the general
// Float shape.
flat_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Float));
}
// The presence of any specific String literal shapes
// subsumes the general String shape.
if flat_shapes
.iter()
.any(|shape| matches!(shape.case.as_ref(), ShapeCase::String(Some(_))))
{
flat_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::String(None)));
}
// Merge arrays and insert into flat_shapes
if !arrays_to_merge.is_empty() {
let longest_prefix_len = arrays_to_merge
.iter()
.fold(0, |acc, (items, _, _)| acc.max(items.len()));
let mut array_locations = Vec::new();
// First, merge the ShapeCase::Array prefix vectors,
// combining overlapping elements using ShapeCase::All.
let fixed_element_shapes = (0..longest_prefix_len)
.map(|i| {
let mut element_shapes = Vec::new();
let mut element_locations = Vec::new();
for (items, rest, locations) in &arrays_to_merge {
array_locations.extend(locations.clone());
element_shapes.push(items.get(i).unwrap_or(rest).clone());
element_locations.extend_from_slice(&items.get(i).unwrap_or(rest).locations);
}
Shape::all(element_shapes, element_locations)
})
.collect::<Vec<_>>();
// Second, merge the ShapeCase::Array rest vectors,
// combining non-None shapes using ShapeCase::All.
let mut rest_shapes_to_merge = Vec::new();
for rest in arrays_to_merge
.iter()
.filter_map(|(_items, rest, _locations)| match rest.case.as_ref() {
ShapeCase::None => None,
_ => Some(rest.clone()),
})
{
extend_or_insert_shape(&mut rest_shapes_to_merge, rest);
}
let merged_rest = if rest_shapes_to_merge.is_empty() {
Shape::none()
} else {
// There are no locations carried forward here because this is a virtual All, not
// one created directly by user code.
all(rest_shapes_to_merge.into_iter(), Vec::new())
};
// Finally, insert the merged ShapeCase::Array into
// flat_shapes.
extend_or_insert_shape(
&mut flat_shapes,
Shape::array(fixed_element_shapes, merged_rest, array_locations),
);
}
// Merge object fields and insert into flat_shapes
if !objects_to_merge.is_empty() {
let mut merged_object_fields = IndexMap::new();
let mut merged_object_rest = Shape::none();
let mut object_locations = Vec::new();
for (fields, rest, locations) in objects_to_merge {
for (field_name, field_shape) in fields {
merged_object_fields
.entry(field_name)
.or_insert_with(Vec::new)
.push(field_shape);
}
object_locations.extend(locations);
merged_object_rest = match (merged_object_rest.case(), rest.case()) {
(ShapeCase::None, _) => rest.clone(),
(_, ShapeCase::None) => merged_object_rest.clone(),
_ => all([merged_object_rest, rest.clone()].into_iter(), Vec::new()),
};
}
flat_shapes.push(Shape::object(
merged_object_fields
.into_iter()
.map(|(k, v)| (k, all(v.into_iter(), Vec::new())))
.collect(),
merged_object_rest,
object_locations,
));
}
// An empty ::All intersection is equivalent to Unknown, since
// it imposes no expectations or criteria on input shapes.
if flat_shapes.is_empty() {
return Shape::unknown(locations);
}
// Remove None from flat_shapes, since it has no marginal effect
// on ::All intersections.
flat_shapes.retain(|shape| !shape.is_none());
// If removing None resulted in empty flat_shapes, return
// None to represent an empty intersection.
if flat_shapes.is_empty() {
return Shape::none();
}
// Similar logic but for Unknown, which also (like None)
// contributes nothing to the intersection.
flat_shapes.retain(|shape| !shape.is_unknown());
if flat_shapes.is_empty() {
return Shape::unknown(locations);
}
// If there's only one shape in the intersection, return it.
if let (Some(only_shape), 1) = (flat_shapes.first(), flat_shapes.len()) {
return only_shape.clone();
}
// To bias simplification towards disjunctive normal form
// (unions of intersections), unpack any ShapeCase::One items
// contained by flat_shapes.
//
// Unpacking the ShapeCase::One items results in a
// ShapeCase::One union of ShapeCase::All shapes (i.e.
// disjunctive normal form) where each ShapeCase::All shape
// represents a distinct choice from each available union,
// treating single non-union shapes as unions of one.
//
// For example
//
// (A | B | C) & D & (E | F) =>
// (A & D & E) | (A & D & F) |
// (B & D & E) | (B & D & F) |
// (C & D & E) | (C & D & F)
//
// Although D is not a ShapeCase::One union, it can be treated
// as a union of just one member shape (D) for the purposes of
// this enumeration.
let new_all_shapes = flat_shapes
.iter()
.fold(vec![vec![]], |acc, shape| {
let mut new_shapes = Vec::new();
for partial_prefix in &acc {
if let ShapeCase::One(one_shapes) = shape.case.as_ref() {
for one_shape in one_shapes {
let mut new_partial = partial_prefix.clone();
if !one_shape.is_none() {
new_partial.push(one_shape.clone());
}
new_shapes.push(new_partial);
}
} else {
let mut new_partial = partial_prefix.clone();
if !shape.is_none() {
new_partial.push(shape.clone());
}
new_shapes.push(new_partial);
}
}
new_shapes
})
.into_iter()
.collect::<IndexSet<_>>();
if new_all_shapes.len() == 1 {
Shape::new(
ShapeCase::All(All {
shapes: flat_shapes,
}),
locations,
)
} else {
let simplified_all_shapes = new_all_shapes
.into_iter()
.map(|shapes| Shape::all(shapes, []))
.collect::<Vec<Shape>>();
Shape::one(simplified_all_shapes, locations)
}
}