shape/simplify.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 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364
use indexmap::IndexMap;
use indexmap::IndexSet;
use super::Shape;
use super::ShapeCase;
impl ShapeCase {
/// Returns a [`Shape`] wrapper around a simplified `ShapeCase`. This
/// function is a primary bottleneck for constructing a [`Shape`], and helps
/// guarantee all [`Shape`] values have been reliably simplified and hashed.
///
/// Note that this method takes ownership of self in order to efficiently
/// return case unmodified in already-simplified cases.
pub fn simplify(self) -> Shape {
match &self {
ShapeCase::One(shapes) => {
if shapes.is_empty() {
return Shape::none();
}
let mut new_shapes = IndexSet::new();
// Flatten any nested `One` shapes
for shape in shapes {
match shape.case.as_ref() {
ShapeCase::One(inner_shapes) => {
for inner_shape in inner_shapes {
new_shapes.insert(inner_shape.clone());
}
}
_ => {
new_shapes.insert(shape.clone());
}
}
}
{
// The presence of the general Bool shape subsumes all
// specific literal boolean shapes.
let boolean_shape = Shape::bool();
if new_shapes.contains(&boolean_shape) {
new_shapes.retain(|shape| {
!matches!(shape.case.as_ref(), ShapeCase::Bool(Some(_)))
});
}
// Also, if new_shapes contains both true and false, then we
// can remove them and simplify the union by adding
// boolean_shape.
//
// Theoretically this same logic could apply to Int or
// String, but that would require somehow forming a union of
// every possible integer or string value.
let true_shape = Shape::bool_value(true);
let false_shape = Shape::bool_value(false);
if new_shapes.contains(&true_shape) && new_shapes.contains(&false_shape) {
new_shapes.insert(boolean_shape.clone());
new_shapes.swap_remove(&true_shape);
new_shapes.shift_remove(&false_shape);
}
}
{
// The presence of the general String shape subsumes all
// specific literal string shapes.
let string_shape = Shape::string();
if new_shapes.contains(&string_shape) {
new_shapes.retain(|shape| {
!matches!(shape.case.as_ref(), ShapeCase::String(Some(_)))
});
}
}
if new_shapes.contains(&Shape::float()) {
// The presence of the general Float shape subsumes all
// general and literal Int shapes.
new_shapes.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Int(_)));
} else if new_shapes.contains(&Shape::int()) {
// The presence of the general Int shape subsumes all
// specific literal int shapes.
new_shapes
.retain(|shape| !matches!(shape.case.as_ref(), ShapeCase::Int(Some(_))));
}
// It's tempting to try to simplify new_shapes further by
// removing any shape that satisfies another shape, since that's
// one interpretation of the cases above: specific primitive
// value shapes like 123 satisfy general primitive shapes like
// Int, and therefore add nothing to the union if the general
// shape is present.
//
// However, in the cases above, the specific value shapes happen
// to be fully subsumed by the general shape, adding no further
// information to the general union. When we're dealing with
// arrays or objects, a shape can satisfy another shape and
// still add information to the union, so information would be
// lost if we removed such shapes here.
//
// For example, since { a: Int } is a more general shape than
// (is satisfied by) { a: Int, b: String }, including { a: Int,
// b: String } in a union with { a: Int } technically does not
// change the set of values represented by the union, but you
// might still like to know that the b field's shape across the
// union is String | None, rather than just None, as it would be
// if we removed the more specific shape from new_shapes.
//
// As a side note, detecting satisfaction among all pairs of
// members of the union is a quadratic operation in the size of
// the union, so it's nice we don't need to do all that work.
// A union of one shape is equivalent to that shape by itself.
if let (Some(only_shape), 1) = (new_shapes.iter().next(), new_shapes.len()) {
return only_shape.clone();
}
if shapes == &new_shapes {
Shape::new_from_simplified(self)
} else {
ShapeCase::One(new_shapes).simplify()
}
}
ShapeCase::All(shapes) => {
let mut flat_shapes = IndexSet::new();
let mut arrays_to_merge = Vec::new();
let mut objects_to_merge = Vec::new();
for shape in shapes {
match shape.case.as_ref() {
// Flatten any nested `All` shapes
ShapeCase::All(inner_shapes) => {
for inner_shape in inner_shapes {
flat_shapes.insert(inner_shape.clone());
}
}
// Store arrays separately so we can merge them into one array
ShapeCase::Array { prefix, tail } => {
arrays_to_merge.push((prefix.clone(), tail.clone()));
}
// Store object fields separately so we can merge them into one object
ShapeCase::Object { fields, rest } => {
objects_to_merge.push((fields.clone(), rest.clone()));
}
_ => {
flat_shapes.insert(shape.clone());
}
}
}
{
// The presence of the null literal shape (ShapeCase::Null)
// in flat_shapes subsumes all the other shapes.
let null_shape = Shape::null();
if flat_shapes.contains(&null_shape) {
return null_shape;
}
}
{
// The presence of any specific Bool literal shapes subsumes
// the general Bool shape.
let boolean_shape = Shape::bool();
if flat_shapes.contains(&boolean_shape)
&& flat_shapes
.iter()
.any(|shape| matches!(shape.case.as_ref(), ShapeCase::Bool(Some(_))))
{
flat_shapes.shift_remove(&boolean_shape);
}
}
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.contains(&Shape::int()) {
// 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.
let string_shape = Shape::string();
if flat_shapes.contains(&string_shape)
&& flat_shapes
.iter()
.any(|shape| matches!(shape.case.as_ref(), ShapeCase::String(Some(_))))
{
flat_shapes.shift_remove(&string_shape);
}
}
// 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()));
// 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();
for (items, rest) in &arrays_to_merge {
element_shapes.push(items.get(i).unwrap_or(rest).clone());
}
Shape::all(&element_shapes)
})
.collect::<Vec<_>>();
// Second, merge the ShapeCase::Array rest vectors,
// combining non-None shapes using ShapeCase::All.
let rest_shapes_to_merge = arrays_to_merge
.iter()
.flat_map(|(_items, rest)| match rest.case.as_ref() {
ShapeCase::None => None,
_ => Some(rest.clone()),
})
.collect::<IndexSet<_>>();
let merged_rest = if rest_shapes_to_merge.is_empty() {
Shape::none()
} else {
ShapeCase::All(rest_shapes_to_merge).simplify()
};
// Finally, insert the merged ShapeCase::Array into
// flat_shapes.
flat_shapes.insert(Shape::array(&fixed_element_shapes, merged_rest));
}
// 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 = ShapeCase::None;
for (fields, rest) in &objects_to_merge {
for (field_name, field_shape) in fields {
merged_object_fields
.entry(field_name.clone())
.or_insert_with(Vec::new)
.push(field_shape.clone());
}
merged_object_rest = match (&merged_object_rest, rest.case.as_ref()) {
(ShapeCase::None, _) => rest.case.as_ref().clone(),
(_, ShapeCase::None) => merged_object_rest.clone(),
_ => ShapeCase::All(
[merged_object_rest.simplify(), rest.clone()]
.into_iter()
.collect(),
),
};
}
flat_shapes.insert(
ShapeCase::Object {
fields: merged_object_fields
.into_iter()
.map(|(k, v)| (k, Shape::all(&v)))
.collect(),
rest: merged_object_rest.simplify(),
}
.simplify(),
);
}
// Remove None from flat_shapes, since None has no marginal
// effect on ::All intersections.
flat_shapes.retain(|shape| !shape.is_none());
// If removing None resulted in empty flat_shapes, return None.
if flat_shapes.is_empty() {
return Shape::none();
}
if let (Some(only_shape), 1) = (flat_shapes.iter().next(), 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 {
match shape.case.as_ref() {
ShapeCase::One(one_shapes) => {
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);
}
}
_ => {
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_from_simplified(ShapeCase::All(flat_shapes))
} else {
let simplified_all_shapes = new_all_shapes
.into_iter()
.map(|shapes| Shape::all(&shapes))
.collect::<Vec<Shape>>();
Shape::one(&simplified_all_shapes)
}
}
ShapeCase::Bool(_)
| ShapeCase::String(_)
| ShapeCase::Int(_)
| ShapeCase::Float
| ShapeCase::Null
| ShapeCase::Array { .. }
| ShapeCase::Object { .. }
| ShapeCase::Name(_, _)
| ShapeCase::Error { .. }
| ShapeCase::None => Shape::new_from_simplified(self),
}
}
}