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

//! This module demonstrates *Orphan rules* and *coherence* of Rust's trait system.
//!
//! # Coherence
//! *Coherence* can informally be understood as a property of trait implementations (typeclass
//! instances) in which the execution semantics does not change with different scopes (contexts).
//!
//! *This definition paraphrases a definition from this
//! [post](http://blog.ezyang.com/2014/07/type-classes-confluence-coherence-global-uniqueness/).*
//!
//! # Global uniqueness of instances
//! This property states that for any type, there is at most one instance resolution for a given
//! type class. An instance violating this property is called the
//! [*orphan instance*](https://wiki.haskell.org/Orphan_instance).
//!
//! In Rust this property is achieved by the *orphan rules* which state that at least one of the
//! following must hold for any crate and `impl Type for Trait`:
//!  1. `Type` is owned (defined) by the implementing crate
//!  1. `Trait` is owned (defined) by the implementing crate
//!
//! *For more see [Chalk's docs](https://rust-lang.github.io/chalk/book/clauses/coherence.html).*
//!
//! # Example: Orphan rule
//! In the example below neither the type [Vec] nor the trait [ToString] is owned by this crate, so
//! the code would create an *orphan instance* which is disallowed and won't compile.
//! ```compile_fail
//! struct Data(String);
//!
//! impl ToString for Vec<Data> {
//!     fn to_string(&self) -> String {
//!         self.iter().map(|data| data.0.clone()).collect::<Vec<_>>().join(" ")
//!     }
//! }
//! ```
//!
//! # Example: Newtype pattern
//! Typical solution to the problem above is the [*newtype*](https://wiki.haskell.org/Newtype)
//! pattern.
//! ```
//! struct Data(String);
//!
//! // The *newtype* for `Vec<Data>`
//! struct DataVec(Vec<Data>);
//!
//! impl ToString for DataVec {
//!     fn to_string(&self) -> String {
//!         self.0.iter().map(|data| data.0.clone()).collect::<Vec<_>>().join(" ")
//!     }
//! }
//! ```
//! In this case `DataVec` is a new type defined in this crate which is enough to satisfy the
//! orphan rules.
//!
//! # Discussion
//!
//! ## Cons
//!  - The ergonomics of defining and using new types is not great. First there's the obvious code
//!    bloat and more importandly the type system doesn't simply generalize all the `impl`s of the
//!    wrapped type which leads to the `self.0` gymnastics.
//!  - Someone might argue that for end applications it might be beneficial to dynamically change
//!    code behavior depending on the implementing module
//!
//! ## Pros
//!  - From a theoretical point of view, function's behavior should not depend on the *scope* in
//!    which it is invoked but rather on the *type* on which it is called (i.e. types should fully
//!    determine behavior)
//!  - This prevents subtle and hard to spot bugs such as the *Hash table problem* or ordering
//!    inversion in certain data structures
//!  - Due to these rules `cargo` can resolve dependencies with two versions of the same crate.
//!    This increases the distribution of development in the Rust ecosystem (for instnance one does
//!    not have to wait for an update of crate X when updating Y when both depend on Z)
//!  - For instance this allows adding extensions to the `std` crate without creating breaking
//!    changes (resulting in a minor or major version change)
//!  - Future Rust could potentially support *Specialization* which would not be possible with
//!    orphan instances (i.e. allow safe ad-hoc behavior for typeclass instances which are strict
//!    subsets of more general ones defined elsewhere)
//!  - The ergonomics of "newtypes" could be improved with something like `#[newtype_deriving]`

/// Module that defines single data type called `Entity`
pub mod model {

    /// Union type which defines two variants [`X`](Entity::X) and [`Y`](Entity::Y)
    #[derive(Debug, PartialEq, Eq)]
    pub enum Entity {
        X,
        Y,
    }
}

/// Module which exposes an operation which depends on an instance of [Ord] for [model::Entity]
pub mod module_a {
    use crate::orphan::model::Entity;
    use std::cmp::Ordering;

    /// Implements [Ord] for [Entity] in which [`X`](Entity::X) > [`Y`](Entity::Y)
    impl Ord for Entity {
        fn cmp(&self, other: &Self) -> Ordering {
            use Entity::*;
            match (self, other) {
                (X, X) | (Y, Y) => Ordering::Equal,
                (X, Y) => Ordering::Greater,
                (Y, X) => Ordering::Less,
            }
        }
    }

    impl PartialOrd for Entity {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    /// Sorts given entities using [Ord] implementation for [Entity] contained in this module
    pub fn prioritize(entities: &mut [Entity]) {
        entities.sort();
    }
}

#[cfg(test)]
mod tests {
    use crate::orphan::model::Entity;
    use crate::orphan::module_a::prioritize;

    #[test]
    fn idempotent_prioritize() {
        let mut entities = vec![Entity::X, Entity::Y];

        prioritize(&mut entities);
        assert_eq!(entities, vec![Entity::Y, Entity::X]);

        prioritize(&mut entities);
        assert_eq!(entities, vec![Entity::Y, Entity::X]);
    }
}

/// This test demonstrates that Rust disallows *Orphan Instances*.
///
/// # Variation of the *Hash table Problem*
/// ```compile_fail
/// pub mod module_b {
///     use crate::orphan::model::Entity;
///     use std::cmp::Ordering;
///
///     // Implements `Ord` for `Entity` in which `X` < `Y`
///     impl Ord for Entity {
///         fn cmp(&self, other: &Self) -> Ordering {
///             use Entity::*;
///             match (self, other) {
///                 (X, X) | (Y, Y) => Ordering::Equal,
///                 (X, Y) => Ordering::Less,
///                 (Y, X) => Ordering::Greater,
///             }
///         }
///     }
///
///     impl PartialOrd for Entity {
///         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
///             Some(self.cmp(other))
///         }
///     }
///
///     // Sorts given entities using `Ord` implementation for `Entity` contained in this module
///     pub fn prioritize(entities: &mut [Entity]) {
///         entities.sort();
///     }
/// }
///
/// #[test]
/// #[should_fail]
/// fn priority_inversion() {
///     use crate::orphan::{model::Entity, module_a, module_b};
///
///     let mut entities = vec![Entity::X, Entity::Y];
///
///     module_a::prioritize(&mut entities);
///     assert_eq!(entities, vec![Entity::Y, Entity::X]);
///
///     module_b::prioritize(&mut entities);
///
///     // This would fail if orphan instances were allowed
///     //  - i.e. the behavior would depend on the *scope* rather than *types*
///     assert_eq!(entities, vec![Entity::Y, Entity::X]);
/// }
/// ```
pub struct OrphanInstanceTest;