Imported Upstream version 1.9.0+dfsg1

[rustc.git] / src / librustc_typeck / variance / constraints.rs

// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Constraint construction and representation
//!
//! The second pass over the AST determines the set of constraints.
//! We walk the set of items and, for each member, generate new constraints.

use dep_graph::DepTrackingMapConfig;
use hir::def_id::DefId;
use middle::resolve_lifetime as rl;
use rustc::ty::subst;
use rustc::ty::subst::ParamSpace;
use rustc::ty::{self, Ty, TyCtxt};
use rustc::ty::maps::ItemVariances;
use rustc::hir::map as hir_map;
use syntax::ast;
use rustc::hir;
use rustc::hir::intravisit::Visitor;

use super::terms::*;
use super::terms::VarianceTerm::*;
use super::terms::ParamKind::*;
use super::xform::*;

pub struct ConstraintContext<'a, 'tcx: 'a> {
    pub terms_cx: TermsContext<'a, 'tcx>,

    // These are pointers to common `ConstantTerm` instances
    covariant: VarianceTermPtr<'a>,
    contravariant: VarianceTermPtr<'a>,
    invariant: VarianceTermPtr<'a>,
    bivariant: VarianceTermPtr<'a>,

    pub constraints: Vec<Constraint<'a>> ,
}

/// Declares that the variable `decl_id` appears in a location with
/// variance `variance`.
#[derive(Copy, Clone)]
pub struct Constraint<'a> {
    pub inferred: InferredIndex,
    pub variance: &'a VarianceTerm<'a>,
}

pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>)
                                            -> ConstraintContext<'a, 'tcx>
{
    let tcx = terms_cx.tcx;
    let covariant = terms_cx.arena.alloc(ConstantTerm(ty::Covariant));
    let contravariant = terms_cx.arena.alloc(ConstantTerm(ty::Contravariant));
    let invariant = terms_cx.arena.alloc(ConstantTerm(ty::Invariant));
    let bivariant = terms_cx.arena.alloc(ConstantTerm(ty::Bivariant));
    let mut constraint_cx = ConstraintContext {
        terms_cx: terms_cx,
        covariant: covariant,
        contravariant: contravariant,
        invariant: invariant,
        bivariant: bivariant,
        constraints: Vec::new(),
    };

    // See README.md for a discussion on dep-graph management.
    tcx.visit_all_items_in_krate(|def_id| ItemVariances::to_dep_node(&def_id),
                                 &mut constraint_cx);

    constraint_cx
}

impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> {
    fn visit_item(&mut self, item: &hir::Item) {
        let tcx = self.terms_cx.tcx;
        let did = tcx.map.local_def_id(item.id);

        debug!("visit_item item={}", tcx.map.node_to_string(item.id));

        match item.node {
            hir::ItemEnum(..) | hir::ItemStruct(..) => {
                let scheme = tcx.lookup_item_type(did);

                // Not entirely obvious: constraints on structs/enums do not
                // affect the variance of their type parameters. See discussion
                // in comment at top of module.
                //
                // self.add_constraints_from_generics(&scheme.generics);

                for field in tcx.lookup_adt_def(did).all_fields() {
                    self.add_constraints_from_ty(&scheme.generics,
                                                 field.unsubst_ty(),
                                                 self.covariant);
                }
            }
            hir::ItemTrait(..) => {
                let trait_def = tcx.lookup_trait_def(did);
                self.add_constraints_from_trait_ref(&trait_def.generics,
                                                    trait_def.trait_ref,
                                                    self.invariant);
            }

            hir::ItemExternCrate(_) |
            hir::ItemUse(_) |
            hir::ItemStatic(..) |
            hir::ItemConst(..) |
            hir::ItemFn(..) |
            hir::ItemMod(..) |
            hir::ItemForeignMod(..) |
            hir::ItemTy(..) |
            hir::ItemImpl(..) |
            hir::ItemDefaultImpl(..) => {
            }
        }
    }
}

/// Is `param_id` a lifetime according to `map`?
fn is_lifetime(map: &hir_map::Map, param_id: ast::NodeId) -> bool {
    match map.find(param_id) {
        Some(hir_map::NodeLifetime(..)) => true, _ => false
    }
}

impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
    fn tcx(&self) -> &'a TyCtxt<'tcx> {
        self.terms_cx.tcx
    }

    fn inferred_index(&self, param_id: ast::NodeId) -> InferredIndex {
        match self.terms_cx.inferred_map.get(&param_id) {
            Some(&index) => index,
            None => {
                bug!("no inferred index entry for {}",
                     self.tcx().map.node_to_string(param_id));
            }
        }
    }

    fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId {
        let tcx = self.terms_cx.tcx;
        assert!(is_lifetime(&tcx.map, param_id));
        match tcx.named_region_map.get(&param_id) {
            Some(&rl::DefEarlyBoundRegion(_, _, lifetime_decl_id))
                => lifetime_decl_id,
            Some(_) => bug!("should not encounter non early-bound cases"),

            // The lookup should only fail when `param_id` is
            // itself a lifetime binding: use it as the decl_id.
            None    => param_id,
        }

    }

    /// Is `param_id` a type parameter for which we infer variance?
    fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool {
        let result = self.terms_cx.inferred_map.contains_key(&param_id);

        // To safe-guard against invalid inferred_map constructions,
        // double-check if variance is inferred at some use of a type
        // parameter (by inspecting parent of its binding declaration
        // to see if it is introduced by a type or by a fn/impl).

        let check_result = |this:&ConstraintContext| -> bool {
            let tcx = this.terms_cx.tcx;
            let decl_id = this.find_binding_for_lifetime(param_id);
            // Currently only called on lifetimes; double-checking that.
            assert!(is_lifetime(&tcx.map, param_id));
            let parent_id = tcx.map.get_parent(decl_id);
            let parent = tcx.map.find(parent_id).unwrap_or_else(
                || bug!("tcx.map missing entry for id: {}", parent_id));

            let is_inferred;
            macro_rules! cannot_happen { () => { {
                bug!("invalid parent: {} for {}",
                     tcx.map.node_to_string(parent_id),
                     tcx.map.node_to_string(param_id));
            } } }

            match parent {
                hir_map::NodeItem(p) => {
                    match p.node {
                        hir::ItemTy(..) |
                        hir::ItemEnum(..) |
                        hir::ItemStruct(..) |
                        hir::ItemTrait(..)   => is_inferred = true,
                        hir::ItemFn(..)      => is_inferred = false,
                        _                    => cannot_happen!(),
                    }
                }
                hir_map::NodeTraitItem(..)   => is_inferred = false,
                hir_map::NodeImplItem(..)    => is_inferred = false,
                _                            => cannot_happen!(),
            }

            return is_inferred;
        };

        assert_eq!(result, check_result(self));

        return result;
    }

    /// Returns a variance term representing the declared variance of the type/region parameter
    /// with the given id.
    fn declared_variance(&self,
                         param_def_id: DefId,
                         item_def_id: DefId,
                         kind: ParamKind,
                         space: ParamSpace,
                         index: usize)
                         -> VarianceTermPtr<'a> {
        assert_eq!(param_def_id.krate, item_def_id.krate);

        if let Some(param_node_id) = self.tcx().map.as_local_node_id(param_def_id) {
            // Parameter on an item defined within current crate:
            // variance not yet inferred, so return a symbolic
            // variance.
            let InferredIndex(index) = self.inferred_index(param_node_id);
            self.terms_cx.inferred_infos[index].term
        } else {
            // Parameter on an item defined within another crate:
            // variance already inferred, just look it up.
            let variances = self.tcx().item_variances(item_def_id);
            let variance = match kind {
                TypeParam => *variances.types.get(space, index),
                RegionParam => *variances.regions.get(space, index),
            };
            self.constant_term(variance)
        }
    }

    fn add_constraint(&mut self,
                      InferredIndex(index): InferredIndex,
                      variance: VarianceTermPtr<'a>) {
        debug!("add_constraint(index={}, variance={:?})",
                index, variance);
        self.constraints.push(Constraint { inferred: InferredIndex(index),
                                           variance: variance });
    }

    fn contravariant(&mut self,
                     variance: VarianceTermPtr<'a>)
                     -> VarianceTermPtr<'a> {
        self.xform(variance, self.contravariant)
    }

    fn invariant(&mut self,
                 variance: VarianceTermPtr<'a>)
                 -> VarianceTermPtr<'a> {
        self.xform(variance, self.invariant)
    }

    fn constant_term(&self, v: ty::Variance) -> VarianceTermPtr<'a> {
        match v {
            ty::Covariant => self.covariant,
            ty::Invariant => self.invariant,
            ty::Contravariant => self.contravariant,
            ty::Bivariant => self.bivariant,
        }
    }

    fn xform(&mut self,
             v1: VarianceTermPtr<'a>,
             v2: VarianceTermPtr<'a>)
             -> VarianceTermPtr<'a> {
        match (*v1, *v2) {
            (_, ConstantTerm(ty::Covariant)) => {
                // Applying a "covariant" transform is always a no-op
                v1
            }

            (ConstantTerm(c1), ConstantTerm(c2)) => {
                self.constant_term(c1.xform(c2))
            }

            _ => {
                &*self.terms_cx.arena.alloc(TransformTerm(v1, v2))
            }
        }
    }

    fn add_constraints_from_trait_ref(&mut self,
                                      generics: &ty::Generics<'tcx>,
                                      trait_ref: ty::TraitRef<'tcx>,
                                      variance: VarianceTermPtr<'a>) {
        debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}",
               trait_ref,
               variance);

        let trait_def = self.tcx().lookup_trait_def(trait_ref.def_id);

        // This edge is actually implied by the call to
        // `lookup_trait_def`, but I'm trying to be future-proof. See
        // README.md for a discussion on dep-graph management.
        self.tcx().dep_graph.read(ItemVariances::to_dep_node(&trait_ref.def_id));

        self.add_constraints_from_substs(
            generics,
            trait_ref.def_id,
            trait_def.generics.types.as_slice(),
            trait_def.generics.regions.as_slice(),
            trait_ref.substs,
            variance);
    }

    /// Adds constraints appropriate for an instance of `ty` appearing
    /// in a context with the generics defined in `generics` and
    /// ambient variance `variance`
    fn add_constraints_from_ty(&mut self,
                               generics: &ty::Generics<'tcx>,
                               ty: Ty<'tcx>,
                               variance: VarianceTermPtr<'a>) {
        debug!("add_constraints_from_ty(ty={:?}, variance={:?})",
               ty,
               variance);

        match ty.sty {
            ty::TyBool |
            ty::TyChar | ty::TyInt(_) | ty::TyUint(_) |
            ty::TyFloat(_) | ty::TyStr => {
                /* leaf type -- noop */
            }

            ty::TyClosure(..) => {
                bug!("Unexpected closure type in variance computation");
            }

            ty::TyRef(region, ref mt) => {
                let contra = self.contravariant(variance);
                self.add_constraints_from_region(generics, *region, contra);
                self.add_constraints_from_mt(generics, mt, variance);
            }

            ty::TyBox(typ) | ty::TyArray(typ, _) | ty::TySlice(typ) => {
                self.add_constraints_from_ty(generics, typ, variance);
            }


            ty::TyRawPtr(ref mt) => {
                self.add_constraints_from_mt(generics, mt, variance);
            }

            ty::TyTuple(ref subtys) => {
                for &subty in subtys {
                    self.add_constraints_from_ty(generics, subty, variance);
                }
            }

            ty::TyEnum(def, substs) |
            ty::TyStruct(def, substs) => {
                let item_type = self.tcx().lookup_item_type(def.did);

                // This edge is actually implied by the call to
                // `lookup_trait_def`, but I'm trying to be future-proof. See
                // README.md for a discussion on dep-graph management.
                self.tcx().dep_graph.read(ItemVariances::to_dep_node(&def.did));

                // All type parameters on enums and structs should be
                // in the TypeSpace.
                assert!(item_type.generics.types.is_empty_in(subst::SelfSpace));
                assert!(item_type.generics.types.is_empty_in(subst::FnSpace));
                assert!(item_type.generics.regions.is_empty_in(subst::SelfSpace));
                assert!(item_type.generics.regions.is_empty_in(subst::FnSpace));

                self.add_constraints_from_substs(
                    generics,
                    def.did,
                    item_type.generics.types.get_slice(subst::TypeSpace),
                    item_type.generics.regions.get_slice(subst::TypeSpace),
                    substs,
                    variance);
            }

            ty::TyProjection(ref data) => {
                let trait_ref = &data.trait_ref;
                let trait_def = self.tcx().lookup_trait_def(trait_ref.def_id);

                // This edge is actually implied by the call to
                // `lookup_trait_def`, but I'm trying to be future-proof. See
                // README.md for a discussion on dep-graph management.
                self.tcx().dep_graph.read(ItemVariances::to_dep_node(&trait_ref.def_id));

                self.add_constraints_from_substs(
                    generics,
                    trait_ref.def_id,
                    trait_def.generics.types.as_slice(),
                    trait_def.generics.regions.as_slice(),
                    trait_ref.substs,
                    variance);
            }

            ty::TyTrait(ref data) => {
                let poly_trait_ref =
                    data.principal_trait_ref_with_self_ty(self.tcx(),
                                                          self.tcx().types.err);

                // The type `Foo<T+'a>` is contravariant w/r/t `'a`:
                let contra = self.contravariant(variance);
                self.add_constraints_from_region(generics, data.bounds.region_bound, contra);

                // Ignore the SelfSpace, it is erased.
                self.add_constraints_from_trait_ref(generics, poly_trait_ref.0, variance);

                let projections = data.projection_bounds_with_self_ty(self.tcx(),
                                                                      self.tcx().types.err);
                for projection in &projections {
                    self.add_constraints_from_ty(generics, projection.0.ty, self.invariant);
                }
            }

            ty::TyParam(ref data) => {
                let def_id = generics.types.get(data.space, data.idx as usize).def_id;
                let node_id = self.tcx().map.as_local_node_id(def_id).unwrap();
                match self.terms_cx.inferred_map.get(&node_id) {
                    Some(&index) => {
                        self.add_constraint(index, variance);
                    }
                    None => {
                        // We do not infer variance for type parameters
                        // declared on methods. They will not be present
                        // in the inferred_map.
                    }
                }
            }

            ty::TyFnDef(_, _, &ty::BareFnTy { ref sig, .. }) |
            ty::TyFnPtr(&ty::BareFnTy { ref sig, .. }) => {
                self.add_constraints_from_sig(generics, sig, variance);
            }

            ty::TyError => {
                // we encounter this when walking the trait references for object
                // types, where we use TyError as the Self type
            }

            ty::TyInfer(..) => {
                bug!("unexpected type encountered in \
                      variance inference: {}", ty);
            }
        }
    }

    /// Adds constraints appropriate for a nominal type (enum, struct,
    /// object, etc) appearing in a context with ambient variance `variance`
    fn add_constraints_from_substs(&mut self,
                                   generics: &ty::Generics<'tcx>,
                                   def_id: DefId,
                                   type_param_defs: &[ty::TypeParameterDef<'tcx>],
                                   region_param_defs: &[ty::RegionParameterDef],
                                   substs: &subst::Substs<'tcx>,
                                   variance: VarianceTermPtr<'a>) {
        debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})",
               def_id,
               substs,
               variance);

        for p in type_param_defs {
            let variance_decl =
                self.declared_variance(p.def_id, def_id, TypeParam,
                                       p.space, p.index as usize);
            let variance_i = self.xform(variance, variance_decl);
            let substs_ty = *substs.types.get(p.space, p.index as usize);
            debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}",
                   variance_decl, variance_i);
            self.add_constraints_from_ty(generics, substs_ty, variance_i);
        }

        for p in region_param_defs {
            let variance_decl =
                self.declared_variance(p.def_id, def_id,
                                       RegionParam, p.space, p.index as usize);
            let variance_i = self.xform(variance, variance_decl);
            let substs_r = *substs.regions.get(p.space, p.index as usize);
            self.add_constraints_from_region(generics, substs_r, variance_i);
        }
    }

    /// Adds constraints appropriate for a function with signature
    /// `sig` appearing in a context with ambient variance `variance`
    fn add_constraints_from_sig(&mut self,
                                generics: &ty::Generics<'tcx>,
                                sig: &ty::PolyFnSig<'tcx>,
                                variance: VarianceTermPtr<'a>) {
        let contra = self.contravariant(variance);
        for &input in &sig.0.inputs {
            self.add_constraints_from_ty(generics, input, contra);
        }
        if let ty::FnConverging(result_type) = sig.0.output {
            self.add_constraints_from_ty(generics, result_type, variance);
        }
    }

    /// Adds constraints appropriate for a region appearing in a
    /// context with ambient variance `variance`
    fn add_constraints_from_region(&mut self,
                                   generics: &ty::Generics<'tcx>,
                                   region: ty::Region,
                                   variance: VarianceTermPtr<'a>) {
        match region {
            ty::ReEarlyBound(ref data) => {
                let def_id =
                    generics.regions.get(data.space, data.index as usize).def_id;
                let node_id = self.tcx().map.as_local_node_id(def_id).unwrap();
                if self.is_to_be_inferred(node_id) {
                    let index = self.inferred_index(node_id);
                    self.add_constraint(index, variance);
                }
            }

            ty::ReStatic => { }

            ty::ReLateBound(..) => {
                // We do not infer variance for region parameters on
                // methods or in fn types.
            }

            ty::ReFree(..) | ty::ReScope(..) | ty::ReVar(..) |
            ty::ReSkolemized(..) | ty::ReEmpty => {
                // We don't expect to see anything but 'static or bound
                // regions when visiting member types or method types.
                bug!("unexpected region encountered in variance \
                      inference: {:?}",
                     region);
            }
        }
    }

    /// Adds constraints appropriate for a mutability-type pair
    /// appearing in a context with ambient variance `variance`
    fn add_constraints_from_mt(&mut self,
                               generics: &ty::Generics<'tcx>,
                               mt: &ty::TypeAndMut<'tcx>,
                               variance: VarianceTermPtr<'a>) {
        match mt.mutbl {
            hir::MutMutable => {
                let invar = self.invariant(variance);
                self.add_constraints_from_ty(generics, mt.ty, invar);
            }

            hir::MutImmutable => {
                self.add_constraints_from_ty(generics, mt.ty, variance);
            }
        }
    }
}