Skip to content

MarkMap::merge_from not always preserving marks on merge #641

Description

@ratmice

Was taking a breather this weekend, from some other projects. Was looking into various #[allow()] lints.

I noticed two, (three?) issues with the MarkMap::merge_from implementation that I wrote.
These unlikely to cause any effect in grmtools, as grmtools always sets marks like required values on the "ours" map then merges a theirs map where the theirs map never has any marks to preserve.

https://github.com/softdevteam/grmtools/blob/master/cfgrammar/src/lib/markmap.rs#L437-L445

  1. in the first if statement in the highlighted code doesn't call, so isn't preserving marks for exclusive merge.
*my_mark = their_mark;
  1. The second issue is that marks can be set on keys, without their presence in the markmap. e.g.
let mut m1 = MarkMap::new();
m1.mark_required(&"foo")
let mut m2 = MarkMap::new();
m1.mark_required(&"bar")
m2.merge_from(m1);
assert!(m2.is_required(&"foo") && m2.is_required(&"bar"));
  1. We currently override marks entirely with = assignment.

It isn't clear that there is a single correct merge behavior for all keys. These various marks get merged together via bitwise operators, so we should be using bitwise operators to preserve the marks on the original map probably.

MarkMap when I originally wrote it was intended as a data structure for rho polymorphic record types, and in that situation it makes sense some marks need to be preserved. But there are probably other marks that should not be preserved.
In the rho polymorphic record case you probably want a mark for the opposite of required x.prohibited(&"baz"), and there it may not make sense that x.merge_from(y) brings in the prohibitions from y, since x itself may contain a baz, and the prohibition is to ensure that they can be merged without conflict. So it doesn't actually make sense to prohibit it, part of the problem here is that this is working based on mutation rather than creating a new merged record.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions