text:
from django.db import migrations, models

class Migration(migrations.Migration):

    dependencies = [
        ("order", "0155_order_should_refresh_prices"),
    ]

    operations = [
        migrations.AddField(
            model_name="order",
            name="tax_exemption",
            field=models.BooleanField(default=False),
        ),
        migrations.RunSQL(
            """
            ALTER TABLE order_order ALTER COLUMN tax_exemption SET DEFAULT
            false;
            """,
            migrations.RunSQL.noop,
        ),
    ]


text:
package org.ehcache.clustered.common.internal.messages;

import org.terracotta.entity.EntityMessage;

/**
 * {@link EntityMessage}s can implement this interface to specify which concurrency key
 * they belong to.
 */
public interface ConcurrentEntityMessage extends EntityMessage {

  /**
   * Get the {@link org.terracotta.entity.EntityMessage}'s concurrency key.
   *
   * @see org.terracotta.entity.ConcurrencyStrategy#concurrencyKey(EntityMessage)
   * @return the concurrency key
   */
  int concurrencyKey();

}

redpajama_set_name: RedPajamaGithub


text:
package lila.socket

import scala.concurrent.duration._
import scala.util.Random

import akka.actor.{ Deploy => _, _ }
import play.api.libs.json._
import play.twirl.api.Html

import actorApi._
import lila.hub.actorApi.{ Deploy, GetUids, GetUserIds }
import lila.memo.ExpireSetMemo

abstract class SocketActor[M <: SocketMember](uidTtl: Duration) extends Socket with Actor {

  val members = scala.collection.mutable.Map.empty[String, M]
  val aliveUids = new ExpireSetMemo(uidTtl)
  var pong = Socket.initialPong

  val lilaBus = context.system.lilaBus

  // this socket is created during application boot
  // and therefore should delay its publication
  // to ensure the listener is ready (sucks, I know)
  val startsOnApplicationBoot: Boolean = false

  override def preStart() {
    if (startsOnApplicationBoot)
      context.system.scheduler.scheduleOnce(1 second) {
        lilaBus.publish(lila.socket.SocketHub.Open(self), 'socket)
      }
    else lilaBus.publish(lila.socket.SocketHub.Open(self), 'socket)
  }

  override def postStop() {
    lilaBus.publish(lila.socket.SocketHub.Close(self), 'socket)
    members.keys foreach eject
  }

  // to be defined in subclassing actor
  def receiveSpecific: Receive

  // generic message handler
  def receiveGeneric: Receive = {

    case Ping(uid)             => ping(uid)

    case Broom                 => broom

    // when a member quits
    case Quit(uid)             => quit(uid)

    case NbMembers(_, pongMsg) => pong = pongMsg

    case GetUids               => sender ! uids

    case GetUserIds            => sender ! userIds

    case Resync(uid)           => resync(uid)

    case d: Deploy             => onDeploy(d)
  }

  def receive = receiveSpecific orElse receiveGeneric

  def notifyAll[A: Writes](t: String, data: A) {
    notifyAll(makeMessage(t, data))
  }

  def notifyAll(t: String) {
    notifyAll(makeMessage(t))
  }

  def notifyAll(msg: JsObject) {
    members.values.foreach(_ push msg)
  }

  def notifyMember[A: Writes](t: String, data: A)(member: M) {
    member push makeMessage(t, data)
  }

  def ping(uid: String) {
    setAlive(uid)
    withMember(uid)(_ push pong)
  }

  def broom {
    members.keys foreach { uid =>
      if (!aliveUids.get(uid)) eject(uid)
    }
  }

  def eject(uid: String) {
    withMember(uid) { member =>
      member.end
      quit(uid)
    }
  }

  def quit(uid: String) {
    members get uid foreach { member =>
      members -= uid
      lilaBus.publish(SocketLeave(uid, member), 'socketDoor)
    }
  }

  def onDeploy(d: Deploy) {
    notifyAll(makeMessage(d.event.key, d.html))
  }

  private val resyncMessage = makeMessage("resync")

  protected def resync(member: M) {
    import scala.concurrent.duration._
    context.system.scheduler.scheduleOnce((Random nextInt 2000).milliseconds) {
      resyncNow(member)
    }
  }

  protected def resync(uid: String) {
    withMember(uid)(resync)
  }

  protected def resyncNow(member: M) {
    member push resyncMessage
  }

  def addMember(uid: String, member: M) {
    eject(uid)
    members += (uid -> member)
    setAlive(uid)
    lilaBus.publish(SocketEnter(uid, member), 'socketDoor)
  }

  def setAlive(uid: String) { aliveUids put uid }

  def uids = members.keys

  def membersByUserId(userId: String): Iterable[M] = members collect {
    case (_, member) if member.userId.contains(userId) => member
  }

  def userIds: Iterable[String] = members.values.flatMap(_.userId)

  def showSpectators(users: List[lila.common.LightUser], nbAnons: Int) = nbAnons match {
    case 0 => users.distinct.map(_.titleName)
    case x => users.distinct.map(_.titleName) :+ ("Anonymous (%d)" format x)
  }

  def withMember(uid: String)(f: M => Unit) {
    members get uid foreach f
  }
}


text:
module Serial #:nodoc:
  module Windows #:nodoc:
    def self.new(com_port, baud, data_bits, stop_bits, parity) #:nodoc:
      # Either specify as 'COM1' or a number. eg 1 for 'COM1'
      begin
        as_int = Integer(com_port)
        com_port = '\\\\.\\COM' + as_int.to_s
      rescue StandardError
        com_port = '\\\\.\\' + com_port.to_s.strip.chomp.upcase
      end

      dcb = Kernel32::DCB.new

      dcb.baud = baud
      dcb.data_bits = data_bits
      dcb.stop_bits = stop_bits
      dcb.parity = parity

      io = File.open(com_port, IO::RDWR|IO::BINARY)
      begin
        io.sync = true
        io.instance_variable_set(:@__serial__port__, com_port[4..-1].to_s.freeze)

        # Sane defaults
        dcb[:Flags] = dcb[:Flags] | (Kernel32::CONSTANTS['FLAGS'].fetch('fDtrControl').fetch(:enable))
        dcb[:XonChar] = 17
        dcb[:XoffChar] = 19

        Kernel32.SetCommState(io, dcb)
        Kernel32.ClearCommError(io)

        # Blocking io
        commtimeouts = Kernel32::COMMTIMEOUTS.new
        commtimeouts[:ReadIntervalTimeout] = Kernel32::CONSTANTS['MAXDWORD']
        commtimeouts[:ReadTotalTimeoutMultiplier] = Kernel32::CONSTANTS['MAXDWORD']
        commtimeouts[:ReadTotalTimeoutConstant] = Kernel32::CONSTANTS['MAXDWORD'] - 1
        commtimeouts[:WriteTotalTimeoutMultiplier] = 0
        commtimeouts[:WriteTotalTimeoutConstant] = Kernel32::CONSTANTS['MAXDWORD'] - 1
        Kernel32.SetCommTimeouts(io, commtimeouts)

        io.extend(self)
      rescue Exception
        begin; io.close; rescue Exception; end
        raise
      end
      io
    end

    def read_timeout
      commtimeouts = Kernel32.GetCommTimeouts(self)
      return -1 if (0 == commtimeouts[:ReadTotalTimeoutConstant])
      return 0 if (Kernel32::CONSTANTS['MAXDWORD'] == commtimeouts[:ReadIntervalTimeout])
      Float(commtimeouts[:ReadTotalTimeoutConstant])/1000.0
    end

    def read_timeout=(val)
      val = Float(val)
      commtimeouts = Kernel32.GetCommTimeouts(self)
      if (0 > val)
        commtimeouts[:ReadIntervalTimeout] = Kernel32::CONSTANTS['MAXDWORD']
        commtimeouts[:ReadTotalTimeoutMultiplier] = 0
        commtimeouts[:ReadTotalTimeoutConstant] = 0
        val = -1
      elsif (0 == val)
        commtimeouts[:ReadIntervalTimeout] = Kernel32::CONSTANTS['MAXDWORD']
        commtimeouts[:ReadTotalTimeoutMultiplier] = Kernel32::CONSTANTS['MAXDWORD']
        commtimeouts[:ReadTotalTimeoutConstant] = Kernel32::CONSTANTS['MAXDWORD'] - 1
        val = 0
      else
        val = (val * 1000.0).to_i
        commtimeouts[:ReadIntervalTimeout] = val
        commtimeouts[:ReadTotalTimeoutMultiplier] = 0
        commtimeouts[:ReadTotalTimeoutConstant] = val
        val = (val / 1000.0)
      end
      Kernel32.SetCommTimeouts(self, commtimeouts); val
    end

    def baud #:nodoc:
      Kernel32.GetCommState(self).baud
    end

    def data_bits #:nodoc:
      Kernel32.GetCommState(self).data_bits
    end

    def stop_bits #:nodoc:
      Kernel32.GetCommState(self).stop_bits
    end

    def parity #:nodoc:
      Kernel32.GetCommState(self).parity
    end

    def read_nonblock(maxlen, outbuf = nil, options = nil) #:nodoc:
      result = Kernel32.nonblock_io(self) { outbuf.nil? ? self.read(maxlen) : self.read(maxlen, outbuf) }
      if result.nil? || (0 == result.length)
        if ((!options.nil?) && (false == options[:exception]))
          return :wait_readable
        end
        raise Errno::EWOULDBLOCK.new
      end
      result
    end

    def readpartial(maxlen, outbuf = nil) #:nodoc:
      ch = self.read(1)
      if (ch.nil? || (0 == ch.length))
        return ch
      end
      self.ungetc(ch)
      Kernel32.nonblock_io(self) { outbuf.nil? ? self.read(maxlen) : self.read(maxlen, outbuf) }
    end

    def readbyte #:nodoc:
      Kernel32.nonblock_io(self) { super }
    end

    def getc #:nodoc:
      Kernel32.nonblock_io(self) { super }
    end

    def readchar #:nodoc:
      Kernel32.nonblock_io(self) { super }
    end

    def to_s #:nodoc:
      ['#<Serial:', @__serial__port__, '>'].join.to_s
    end

    def inspect #:nodoc:
      self.to_s
    end

    ##
    # FFI integration with Kernel32.dll to provide access to OS specific serial port APIs
    module Kernel32 #:nodoc:
      require 'ffi'

      extend FFI::Library #:nodoc:
      ffi_lib 'kernel32'
      ffi_convention :stdcall

      def self.GetCommState(ruby_io) #:nodoc:
        dcb = DCB.new
        dcb[:DCBlength] = dcb.size
        return dcb unless (0 == c_GetCommState(LIBC._get_osfhandle(ruby_io), dcb))
        raise ERRNO[FFI.errno].new
      end

      def self.SetCommState(ruby_io, dcb) #:nodoc:
        dcb[:DCBlength] = dcb.size
        dcb[:Flags] = dcb[:Flags] | 1 # fBinary must be true
        return true unless (0 == c_SetCommState(LIBC._get_osfhandle(ruby_io), dcb))
        raise ERRNO[FFI.errno].new
      end

      def self.GetCommTimeouts(ruby_io) #:nodoc:
        commtimeouts = COMMTIMEOUTS.new
        return commtimeouts unless (0 == c_GetCommTimeouts(LIBC._get_osfhandle(ruby_io), commtimeouts))
        raise ERRNO[FFI.errno].new
      end

      def self.SetCommTimeouts(ruby_io, commtimeouts) #:nodoc:
        return true unless (0 == c_SetCommTimeouts(LIBC._get_osfhandle(ruby_io), commtimeouts))
        raise ERRNO[FFI.errno].new
      end

      def self.ClearCommError(ruby_io) #:nodoc:
        return true unless (0 == c_ClearCommError(LIBC._get_osfhandle(ruby_io), 0, 0))
        raise ERRNO[FFI.errno].new
      end

      def self.nonblock_io(ruby_io, &blk)
        return nil if blk.nil?
        commtimeouts = self.GetCommTimeouts(ruby_io)
        self.SetCommTimeouts(ruby_io, (@@read_nonblock_io ||= begin
          timeouts = COMMTIMEOUTS.new
          timeouts[:ReadIntervalTimeout] = CONSTANTS['MAXDWORD']
          timeouts[:ReadTotalTimeoutMultiplier] = 0
          timeouts[:ReadTotalTimeoutConstant] = 0
          timeouts[:WriteTotalTimeoutMultiplier] = 1
          timeouts[:WriteTotalTimeoutConstant] = 1
          timeouts
        end))
        begin
          blk.yield
        ensure
          self.SetCommTimeouts(ruby_io, commtimeouts)
        end
      end

      class DCB < FFI::Struct #:nodoc:
        layout :DCBlength, :uint32,
               :BaudRate, :uint32,
               :Flags, :uint32,
               :wReserved, :uint16,
               :XonLim, :uint16,
               :XoffLim, :uint16,
               :ByteSize, :uint8,
               :Parity, :uint8,
               :StopBits, :uint8,
               :XonChar, :int8,
               :XoffChar, :int8,
               :ErrorChar, :int8,
               :EofChar, :int8,
               :EvtChar, :int8,
               :wReserved1, :uint16

        def baud=(val) #:nodoc:
          new_val = begin
            Integer(val)
          rescue StandardError
            -1
          end
          if (0 >= new_val)
            raise ArgumentError.new "Invalid baud, specify a positive Integer"
          end
          self[:BaudRate] = new_val; val
        end

        def baud #:nodoc:
          self[:BaudRate]
        end

        def data_bits=(val) #:nodoc:
          parsed = CONSTANTS['DATA_BITS'].fetch(val, nil)
          if parsed.nil?
            raise ArgumentError.new "Invalid data bits, supported values #{CONSTANTS['DATA_BITS'].keys.inspect}"
          end
          self[:ByteSize] = parsed; val
        end

        def data_bits #:nodoc:
          CONSTANTS['DATA_BITS_'].fetch(self[:ByteSize])
        end

        def stop_bits=(val) #:nodoc:
          parsed = CONSTANTS['STOP_BITS'].fetch(val, nil)
          if parsed.nil?
            raise ArgumentError.new "Invalid data bits, supported values #{CONSTANTS['STOP_BITS'].keys.inspect}"
          end
          self[:StopBits] = parsed; val
        end

        def stop_bits #:nodoc:
          CONSTANTS['STOP_BITS_'].fetch(self[:StopBits])
        end

        def parity=(val) #:nodoc:
          parsed = CONSTANTS['PARITY'].fetch(val, nil)
          if parsed.nil?
            raise ArgumentError.new "Invalid parity, supported values #{CONSTANTS['PARITY'].keys.inspect}"
          end
          if (:none == val)
            self[:Flags] = self[:Flags] & (~CONSTANTS['FLAGS'].fetch('fParity'))
          else
            self[:Flags] = self[:Flags] | CONSTANTS['FLAGS'].fetch('fParity')
          end
          self[:Parity] = parsed; val
        end

        def parity #:nodoc:
          CONSTANTS['PARITY_'].fetch(self[:Parity])
        end
      end

      class COMMTIMEOUTS < FFI::Struct #:nodoc:
        layout :ReadIntervalTimeout, :uint32,
               :ReadTotalTimeoutMultiplier, :uint32,
               :ReadTotalTimeoutConstant, :uint32,
               :WriteTotalTimeoutMultiplier, :uint32,
               :WriteTotalTimeoutConstant, :uint32
      end

      CONSTANTS ||= begin #:nodoc:
        constants = {
          'MAXDWORD' => 4294967295,
          'DATA_BITS' => { 5 => 5, 6 => 6, 7 => 7, 8 => 8 }.freeze,
          'STOP_BITS' => { 1 => 0, 1.5 => 1, 2 => 2 }.freeze,
          'PARITY' => { none: 0, odd: 1, even: 2, mark: 3, space: 4 }.freeze,
          'FLAGS' => {
            'fParity' => 2, 'fOutxCtsFlow' => 4, 'fOutxDsrFlow' => 8,
            'fDtrControl' => { disable: 0, enable: 16, handshake: 32 }.freeze,
            'fDsrSensitivity' => 64, 'fTXContinueOnXoff' => 128, 'fOutX' => 256,
            'fInX' => 512, 'fErrorChar' => 1024, 'fNull' => 2048,
            'fRtsControl' => { disable: 0, enable: 4096, handshake: 8192,  toggle: 12288 }.freeze,
            'fAbortOnError' => 16384
          }.freeze,
        }

        constants['DATA_BITS_'] = constants['DATA_BITS'].each_with_object({}) { |(k,v),r| r[v] = k }.freeze
        constants['STOP_BITS_'] = constants['STOP_BITS'].each_with_object({}) { |(k,v),r| r[v] = k }.freeze
        constants['PARITY_'] = constants['PARITY'].each_with_object({}) { |(k,v),r| r[v] = k }.freeze
        constants['FLAGS_'] = {}
        constants['FLAGS_']['fDtrControl'] = constants['FLAGS']['fDtrControl'].each_with_object({}) { |(k,v),r| r[v] = k }.freeze
        constants['FLAGS_']['fRtsControl'] = constants['FLAGS']['fRtsControl'].each_with_object({}) { |(k,v),r| r[v] = k }.freeze
        constants['FLAGS_'].freeze

        constants.freeze
      end

      module LIBC #:nodoc:
        extend FFI::Library #:nodoc:
        ffi_lib FFI::Library::LIBC

        def self._get_osfhandle(ruby_io) #:nodoc:
          handle = c__get_osfhandle(ruby_io.fileno)
          return handle unless (-1 == handle)
          raise ERRNO[FFI.errno].new
        end

        attach_function :c__get_osfhandle, :_get_osfhandle, [:int], :long #:nodoc:
        private_class_method :c__get_osfhandle #:nodoc:
      end

      ERRNO ||= Errno.constants.each_with_object({}) { |e, r| e = Errno.const_get(e); r[e::Errno] = e }.freeze #:nodoc:

      attach_function :c_GetCommState, :GetCommState, [:long, :buffer_out], :int32 #:nodoc:
      attach_function :c_SetCommState, :SetCommState, [:long, :buffer_in], :int32 #:nodoc:
      attach_function :c_GetCommTimeouts, :GetCommTimeouts, [:long, :buffer_out], :int32 #:nodoc:
      attach_function :c_SetCommTimeouts, :SetCommTimeouts, [:long, :buffer_in], :int32 #:nodoc:
      attach_function :c_ClearCommError, :ClearCommError, [:long, :int, :int], :int32 #:nodoc:
      private_class_method :c_GetCommState, :c_SetCommState, :c_GetCommTimeouts, :c_SetCommTimeouts, :c_ClearCommError #:nodoc:
      private_constant :LIBC, :ERRNO #:nodoc:
    end

    private_constant :Kernel32 #:nodoc:
  end
end


text:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace NuGet.PackageManagement.VisualStudio
{
    public abstract class SettingsManagerBase
    {
        private readonly ISettingsManager _settingsManager;

        protected SettingsManagerBase(IServiceProvider serviceProvider)
        {
            if (serviceProvider == null)
            {
                throw new ArgumentNullException("serviceProvider");
            }

            _settingsManager = new SettingsManagerWrapper(serviceProvider);
        }

        protected bool ReadBool(string settingsRoot, string property, bool defaultValue = false)
        {
            var userSettingsStore = _settingsManager.GetReadOnlySettingsStore();
            if (userSettingsStore != null && userSettingsStore.CollectionExists(settingsRoot))
            {
                return userSettingsStore.GetBoolean(settingsRoot, property, defaultValue);
            }
            else
            {
                return defaultValue;
            }
        }

        protected void WriteBool(string settingsRoot, string property, bool value)
        {
            IWritableSettingsStore userSettingsStore = GetWritableSettingsStore(settingsRoot);
            if (userSettingsStore != null)
            {
                userSettingsStore.SetBoolean(settingsRoot, property, value);
            }
        }

        protected int ReadInt32(string settingsRoot, string property, int defaultValue = 0)
        {
            var userSettingsStore = _settingsManager.GetReadOnlySettingsStore();
            if (userSettingsStore != null && userSettingsStore.CollectionExists(settingsRoot))
            {
                return userSettingsStore.GetInt32(settingsRoot, property, defaultValue);
            }
            else
            {
                return defaultValue;
            }
        }

        protected void WriteInt32(string settingsRoot, string property, int value)
        {
            IWritableSettingsStore userSettingsStore = GetWritableSettingsStore(settingsRoot);
            if (userSettingsStore != null)
            {
                userSettingsStore.SetInt32(settingsRoot, property, value);
            }
        }

        protected string ReadString(string settingsRoot, string property, string defaultValue = "")
        {
            var userSettingsStore = _settingsManager.GetReadOnlySettingsStore();
            if (userSettingsStore != null && userSettingsStore.CollectionExists(settingsRoot))
            {
                return userSettingsStore.GetString(settingsRoot, property, defaultValue);
            }
            else
            {
                return defaultValue;
            }
        }

        protected string[] ReadStrings(string settingsRoot, string[] properties, string defaultValue = "")
        {
            var userSettingsStore = _settingsManager.GetReadOnlySettingsStore();
            if (userSettingsStore != null && userSettingsStore.CollectionExists(settingsRoot))
            {
                string[] values = new string[properties.Length];
                for (int i = 0; i < values.Length; i++)
                {
                    values[i] = userSettingsStore.GetString(settingsRoot, properties[i], defaultValue);
                }
                return values;
            }
            else
            {
                return null;
            }
        }

        protected bool DeleteProperty(string settingsRoot, string property)
        {
            IWritableSettingsStore userSettingsStore = GetWritableSettingsStore(settingsRoot);
            if (userSettingsStore != null)
            {
                return userSettingsStore.DeleteProperty(settingsRoot, property);
            }
            else
            {
                return false;
            }
        }

        protected void WriteStrings(string settingsRoot, string[] properties, string[] values)
        {
            Debug.Assert(properties.Length == values.Length);

            IWritableSettingsStore userSettingsStore = GetWritableSettingsStore(settingsRoot);
            if (userSettingsStore != null)
            {
                for (int i = 0; i < properties.Length; i++)
                {
                    userSettingsStore.SetString(settingsRoot, properties[i], values[i]);
                }
            }
        }

        protected void WriteString(string settingsRoot, string property, string value)
        {
            IWritableSettingsStore userSettingsStore = GetWritableSettingsStore(settingsRoot);
            if (userSettingsStore != null)
            {
                userSettingsStore.SetString(settingsRoot, property, value);
            }
        }

        protected void ClearAllSettings(string settingsRoot)
        {
            IWritableSettingsStore userSettingsStore = _settingsManager.GetWritableSettingsStore();
            if (userSettingsStore != null && userSettingsStore.CollectionExists(settingsRoot))
            {
                userSettingsStore.DeleteCollection(settingsRoot);
            }
        }

        private IWritableSettingsStore GetWritableSettingsStore(string settingsRoot)
        {
            IWritableSettingsStore userSettingsStore = _settingsManager.GetWritableSettingsStore();
            if (userSettingsStore != null && !userSettingsStore.CollectionExists(settingsRoot))
            {
                userSettingsStore.CreateCollection(settingsRoot);
            }
            return userSettingsStore;
        }
    }
}


text:
// Copyright 2012-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.

/*!

Error Reporting Code for the inference engine

Because of the way inference, and in particular region inference,
works, it often happens that errors are not detected until far after
the relevant line of code has been type-checked. Therefore, there is
an elaborate system to track why a particular constraint in the
inference graph arose so that we can explain to the user what gave
rise to a patricular error.

The basis of the system are the "origin" types. An "origin" is the
reason that a constraint or inference variable arose. There are
different "origin" enums for different kinds of constraints/variables
(e.g., `TypeOrigin`, `RegionVariableOrigin`). An origin always has
a span, but also more information so that we can generate a meaningful
error message.

Having a catalogue of all the different reasons an error can arise is
also useful for other reasons, like cross-referencing FAQs etc, though
we are not really taking advantage of this yet.

# Region Inference

Region inference is particularly tricky because it always succeeds "in
the moment" and simply registers a constraint. Then, at the end, we
can compute the full graph and report errors, so we need to be able to
store and later report what gave rise to the conflicting constraints.

# Subtype Trace

Determing whether `T1 <: T2` often involves a number of subtypes and
subconstraints along the way. A "TypeTrace" is an extended version
of an origin that traces the types and other values that were being
compared. It is not necessarily comprehensive (in fact, at the time of
this writing it only tracks the root values being compared) but I'd
like to extend it to include significant "waypoints". For example, if
you are comparing `(T1, T2) <: (T3, T4)`, and the problem is that `T2
<: T4` fails, I'd like the trace to include enough information to say
"in the 2nd element of the tuple". Similarly, failures when comparing
arguments or return types in fn types should be able to cite the
specific position, etc.

# Reality vs plan

Of course, there is still a LOT of code in typeck that has yet to be
ported to this system, and which relies on string concatenation at the
time of error detection.

*/

use collections::HashSet;
use middle::ty;
use middle::ty::{Region, ReFree};
use middle::typeck::infer;
use middle::typeck::infer::InferCtxt;
use middle::typeck::infer::TypeTrace;
use middle::typeck::infer::SubregionOrigin;
use middle::typeck::infer::RegionVariableOrigin;
use middle::typeck::infer::ValuePairs;
use middle::typeck::infer::region_inference::RegionResolutionError;
use middle::typeck::infer::region_inference::ConcreteFailure;
use middle::typeck::infer::region_inference::SubSupConflict;
use middle::typeck::infer::region_inference::SupSupConflict;
use middle::typeck::infer::region_inference::ProcessedErrors;
use middle::typeck::infer::region_inference::SameRegions;
use std::cell::{Cell, RefCell};
use std::char::from_u32;
use std::rc::Rc;
use std::string::String;
use syntax::ast;
use syntax::ast_map;
use syntax::ast_util;
use syntax::ast_util::name_to_dummy_lifetime;
use syntax::owned_slice::OwnedSlice;
use syntax::codemap;
use syntax::parse::token;
use syntax::print::pprust;
use util::ppaux::UserString;
use util::ppaux::bound_region_to_str;
use util::ppaux::note_and_explain_region;

pub trait ErrorReporting {
    fn report_region_errors(&self,
                            errors: &Vec<RegionResolutionError>);

    fn process_errors(&self, errors: &Vec<RegionResolutionError>)
                      -> Vec<RegionResolutionError>;

    fn report_type_error(&self, trace: TypeTrace, terr: &ty::type_err);

    fn report_and_explain_type_error(&self,
                                     trace: TypeTrace,
                                     terr: &ty::type_err);

    fn values_str(&self, values: &ValuePairs) -> Option<String>;

    fn expected_found_str<T:UserString+Resolvable>(
        &self,
        exp_found: &ty::expected_found<T>)
        -> Option<String>;

    fn report_concrete_failure(&self,
                               origin: SubregionOrigin,
                               sub: Region,
                               sup: Region);

    fn report_sub_sup_conflict(&self,
                               var_origin: RegionVariableOrigin,
                               sub_origin: SubregionOrigin,
                               sub_region: Region,
                               sup_origin: SubregionOrigin,
                               sup_region: Region);

    fn report_sup_sup_conflict(&self,
                               var_origin: RegionVariableOrigin,
                               origin1: SubregionOrigin,
                               region1: Region,
                               origin2: SubregionOrigin,
                               region2: Region);

    fn report_processed_errors(&self,
                               var_origin: &[RegionVariableOrigin],
                               trace_origin: &[(TypeTrace, ty::type_err)],
                               same_regions: &[SameRegions]);

    fn give_suggestion(&self, same_regions: &[SameRegions]);
}

trait ErrorReportingHelpers {
    fn report_inference_failure(&self,
                                var_origin: RegionVariableOrigin);

    fn note_region_origin(&self,
                          origin: SubregionOrigin);

    fn give_expl_lifetime_param(&self,
                                decl: &ast::FnDecl,
                                fn_style: ast::FnStyle,
                                ident: ast::Ident,
                                opt_explicit_self: Option<ast::ExplicitSelf_>,
                                generics: &ast::Generics,
                                span: codemap::Span);
}

impl<'a> ErrorReporting for InferCtxt<'a> {
    fn report_region_errors(&self,
                            errors: &Vec<RegionResolutionError>) {
        let p_errors = self.process_errors(errors);
        let errors = if p_errors.is_empty() { errors } else { &p_errors };
        for error in errors.iter() {
            match error.clone() {
                ConcreteFailure(origin, sub, sup) => {
                    self.report_concrete_failure(origin, sub, sup);
                }

                SubSupConflict(var_origin,
                               sub_origin, sub_r,
                               sup_origin, sup_r) => {
                    self.report_sub_sup_conflict(var_origin,
                                                 sub_origin, sub_r,
                                                 sup_origin, sup_r);
                }

                SupSupConflict(var_origin,
                               origin1, r1,
                               origin2, r2) => {
                    self.report_sup_sup_conflict(var_origin,
                                                 origin1, r1,
                                                 origin2, r2);
                }

                ProcessedErrors(ref var_origins,
                                ref trace_origins,
                                ref same_regions) => {
                    if !same_regions.is_empty() {
                        self.report_processed_errors(var_origins.as_slice(),
                                                     trace_origins.as_slice(),
                                                     same_regions.as_slice());
                    }
                }
            }
        }
    }

    // This method goes through all the errors and try to group certain types
    // of error together, for the purpose of suggesting explicit lifetime
    // parameters to the user. This is done so that we can have a more
    // complete view of what lifetimes should be the same.
    // If the return value is an empty vector, it means that processing
    // failed (so the return value of this method should not be used)
    fn process_errors(&self, errors: &Vec<RegionResolutionError>)
                      -> Vec<RegionResolutionError> {
        debug!("process_errors()");
        let mut var_origins = Vec::new();
        let mut trace_origins = Vec::new();
        let mut same_regions = Vec::new();
        let mut processed_errors = Vec::new();
        for error in errors.iter() {
            match error.clone() {
                ConcreteFailure(origin, sub, sup) => {
                    debug!("processing ConcreteFailure")
                    let trace = match origin {
                        infer::Subtype(trace) => Some(trace),
                        _ => None,
                    };
                    match free_regions_from_same_fn(self.tcx, sub, sup) {
                        Some(ref same_frs) if trace.is_some() => {
                            let trace = trace.unwrap();
                            let terr = ty::terr_regions_does_not_outlive(sup,
                                                                         sub);
                            trace_origins.push((trace, terr));
                            append_to_same_regions(&mut same_regions, same_frs);
                        }
                        _ => processed_errors.push((*error).clone()),
                    }
                }
                SubSupConflict(var_origin, _, sub_r, _, sup_r) => {
                    debug!("processing SubSupConflict")
                    match free_regions_from_same_fn(self.tcx, sub_r, sup_r) {
                        Some(ref same_frs) => {
                            var_origins.push(var_origin);
                            append_to_same_regions(&mut same_regions, same_frs);
                        }
                        None => processed_errors.push((*error).clone()),
                    }
                }
                SupSupConflict(..) => processed_errors.push((*error).clone()),
                _ => ()  // This shouldn't happen
            }
        }
        if !same_regions.is_empty() {
            let common_scope_id = same_regions.get(0).scope_id;
            for sr in same_regions.iter() {
                // Since ProcessedErrors is used to reconstruct the function
                // declaration, we want to make sure that they are, in fact,
                // from the same scope
                if sr.scope_id != common_scope_id {
                    debug!("returning empty result from process_errors because
                            {} != {}", sr.scope_id, common_scope_id);
                    return vec!();
                }
            }
            let pe = ProcessedErrors(var_origins, trace_origins, same_regions);
            debug!("errors processed: {:?}", pe);
            processed_errors.push(pe);
        }
        return processed_errors;

        struct FreeRegionsFromSameFn {
            sub_fr: ty::FreeRegion,
            sup_fr: ty::FreeRegion,
            scope_id: ast::NodeId
        }

        impl FreeRegionsFromSameFn {
            fn new(sub_fr: ty::FreeRegion,
                   sup_fr: ty::FreeRegion,
                   scope_id: ast::NodeId)
                   -> FreeRegionsFromSameFn {
                FreeRegionsFromSameFn {
                    sub_fr: sub_fr,
                    sup_fr: sup_fr,
                    scope_id: scope_id
                }
            }
        }

        fn free_regions_from_same_fn(tcx: &ty::ctxt,
                                     sub: Region,
                                     sup: Region)
                                     -> Option<FreeRegionsFromSameFn> {
            debug!("free_regions_from_same_fn(sub={:?}, sup={:?})", sub, sup);
            let (scope_id, fr1, fr2) = match (sub, sup) {
                (ReFree(fr1), ReFree(fr2)) => {
                    if fr1.scope_id != fr2.scope_id {
                        return None
                    }
                    assert!(fr1.scope_id == fr2.scope_id);
                    (fr1.scope_id, fr1, fr2)
                },
                _ => return None
            };
            let parent = tcx.map.get_parent(scope_id);
            let parent_node = tcx.map.find(parent);
            match parent_node {
                Some(node) => match node {
                    ast_map::NodeItem(item) => match item.node {
                        ast::ItemFn(..) => {
                            Some(FreeRegionsFromSameFn::new(fr1, fr2, scope_id))
                        },
                        _ => None
                    },
                    ast_map::NodeMethod(..) => {
                        Some(FreeRegionsFromSameFn::new(fr1, fr2, scope_id))
                    },
                    _ => None
                },
                None => {
                    debug!("no parent node of scope_id {}", scope_id)
                    None
                }
            }
        }

        fn append_to_same_regions(same_regions: &mut Vec<SameRegions>,
                                  same_frs: &FreeRegionsFromSameFn) {
            let scope_id = same_frs.scope_id;
            let (sub_fr, sup_fr) = (same_frs.sub_fr, same_frs.sup_fr);
            for sr in same_regions.mut_iter() {
                if sr.contains(&sup_fr.bound_region)
                   && scope_id == sr.scope_id {
                    sr.push(sub_fr.bound_region);
                    return
                }
            }
            same_regions.push(SameRegions {
                scope_id: scope_id,
                regions: vec!(sub_fr.bound_region, sup_fr.bound_region)
            })
        }
    }

    fn report_type_error(&self, trace: TypeTrace, terr: &ty::type_err) {
        let expected_found_str = match self.values_str(&trace.values) {
            Some(v) => v,
            None => {
                return; /* derived error */
            }
        };

        let message_root_str = match trace.origin {
            infer::Misc(_) => "mismatched types",
            infer::MethodCompatCheck(_) => "method not compatible with trait",
            infer::ExprAssignable(_) => "mismatched types",
            infer::RelateTraitRefs(_) => "mismatched traits",
            infer::RelateSelfType(_) => "mismatched types",
            infer::MatchExpressionArm(_, _) => "match arms have incompatible types",
            infer::IfExpression(_) => "if and else have incompatible types",
        };

        self.tcx.sess.span_err(
            trace.origin.span(),
            format!("{}: {} ({})",
                 message_root_str,
                 expected_found_str,
                 ty::type_err_to_str(self.tcx, terr)).as_slice());

        match trace.origin {
            infer::MatchExpressionArm(_, arm_span) =>
                self.tcx.sess.span_note(arm_span, "match arm with an incompatible type"),
            _ => ()
        }
    }

    fn report_and_explain_type_error(&self,
                                     trace: TypeTrace,
                                     terr: &ty::type_err) {
        self.report_type_error(trace, terr);
        ty::note_and_explain_type_err(self.tcx, terr);
    }

    fn values_str(&self, values: &ValuePairs) -> Option<String> {
        /*!
         * Returns a string of the form "expected `{}` but found `{}`",
         * or None if this is a derived error.
         */
        match *values {
            infer::Types(ref exp_found) => {
                self.expected_found_str(exp_found)
            }
            infer::TraitRefs(ref exp_found) => {
                self.expected_found_str(exp_found)
            }
        }
    }

    fn expected_found_str<T:UserString+Resolvable>(
        &self,
        exp_found: &ty::expected_found<T>)
        -> Option<String>
    {
        let expected = exp_found.expected.resolve(self);
        if expected.contains_error() {
            return None;
        }

        let found = exp_found.found.resolve(self);
        if found.contains_error() {
            return None;
        }

        Some(format!("expected `{}` but found `{}`",
                     expected.user_string(self.tcx),
                     found.user_string(self.tcx)))
    }

    fn report_concrete_failure(&self,
                               origin: SubregionOrigin,
                               sub: Region,
                               sup: Region) {
        match origin {
            infer::Subtype(trace) => {
                let terr = ty::terr_regions_does_not_outlive(sup, sub);
                self.report_and_explain_type_error(trace, &terr);
            }
            infer::Reborrow(span) => {
                self.tcx.sess.span_err(
                    span,
                    "lifetime of reference outlines \
                     lifetime of borrowed content...");
                note_and_explain_region(
                    self.tcx,
                    "...the reference is valid for ",
                    sub,
                    "...");
                note_and_explain_region(
                    self.tcx,
                    "...but the borrowed content is only valid for ",
                    sup,
                    "");
            }
            infer::ReborrowUpvar(span, ref upvar_id) => {
                self.tcx.sess.span_err(
                    span,
                    format!("lifetime of borrowed pointer outlives \
                            lifetime of captured variable `{}`...",
                            ty::local_var_name_str(self.tcx,
                                                   upvar_id.var_id)
                                .get()
                                .to_str()).as_slice());
                note_and_explain_region(
                    self.tcx,
                    "...the borrowed pointer is valid for ",
                    sub,
                    "...");
                note_and_explain_region(
                    self.tcx,
                    format!("...but `{}` is only valid for ",
                            ty::local_var_name_str(self.tcx,
                                                   upvar_id.var_id)
                                .get()
                                .to_str()).as_slice(),
                    sup,
                    "");
            }
            infer::InfStackClosure(span) => {
                self.tcx.sess.span_err(
                    span,
                    "closure outlives stack frame");
                note_and_explain_region(
                    self.tcx,
                    "...the closure must be valid for ",
                    sub,
                    "...");
                note_and_explain_region(
                    self.tcx,
                    "...but the closure's stack frame is only valid for ",
                    sup,
                    "");
            }
            infer::InvokeClosure(span) => {
                self.tcx.sess.span_err(
                    span,
                    "cannot invoke closure outside of its lifetime");
                note_and_explain_region(
                    self.tcx,
                    "the closure is only valid for ",
                    sup,
                    "");
            }
            infer::DerefPointer(span) => {
                self.tcx.sess.span_err(
                    span,
                    "dereference of reference outside its lifetime");
                note_and_explain_region(
                    self.tcx,
                    "the reference is only valid for ",
                    sup,
                    "");
            }
            infer::FreeVariable(span, id) => {
                self.tcx.sess.span_err(
                    span,
                    format!("captured variable `{}` does not \
                            outlive the enclosing closure",
                            ty::local_var_name_str(self.tcx,
                                                   id).get()
                                                      .to_str()).as_slice());
                note_and_explain_region(
                    self.tcx,
                    "captured variable is valid for ",
                    sup,
                    "");
                note_and_explain_region(
                    self.tcx,
                    "closure is valid for ",
                    sub,
                    "");
            }
            infer::IndexSlice(span) => {
                self.tcx.sess.span_err(span,
                                       "index of slice outside its lifetime");
                note_and_explain_region(
                    self.tcx,
                    "the slice is only valid for ",
                    sup,
                    "");
            }
            infer::RelateObjectBound(span) => {
                self.tcx.sess.span_err(
                    span,
                    "lifetime of the source pointer does not outlive \
                     lifetime bound of the object type");
                note_and_explain_region(
                    self.tcx,
                    "object type is valid for ",
                    sub,
                    "");
                note_and_explain_region(
                    self.tcx,
                    "source pointer is only valid for ",
                    sup,
                    "");
            }
            infer::CallRcvr(span) => {
                self.tcx.sess.span_err(
                    span,
                    "lifetime of method receiver does not outlive \
                     the method call");
                note_and_explain_region(
                    self.tcx,
                    "the receiver is only valid for ",
                    sup,
                    "");
            }
            infer::CallArg(span) => {
                self.tcx.sess.span_err(
                    span,
                    "lifetime of function argument does not outlive \
                     the function call");
                note_and_explain_region(
                    self.tcx,
                    "the function argument is only valid for ",
                    sup,
                    "");
            }
            infer::CallReturn(span) => {
                self.tcx.sess.span_err(
                    span,
                    "lifetime of return value does not outlive \
                     the function call");
                note_and_explain_region(
                    self.tcx,
                    "the return value is only valid for ",
                    sup,
                    "");
            }
            infer::AddrOf(span) => {
                self.tcx.sess.span_err(
                    span,
                    "reference is not valid \
                     at the time of borrow");
                note_and_explain_region(
                    self.tcx,
                    "the borrow is only valid for ",
                    sup,
                    "");
            }
            infer::AutoBorrow(span) => {
                self.tcx.sess.span_err(
                    span,
                    "automatically reference is not valid \
                     at the time of borrow");
                note_and_explain_region(
                    self.tcx,
                    "the automatic borrow is only valid for ",
                    sup,
                    "");
            }
            infer::BindingTypeIsNotValidAtDecl(span) => {
                self.tcx.sess.span_err(
                    span,
                    "lifetime of variable does not enclose its declaration");
                note_and_explain_region(
                    self.tcx,
                    "the variable is only valid for ",
                    sup,
                    "");
            }
            infer::ReferenceOutlivesReferent(ty, span) => {
                self.tcx.sess.span_err(
                    span,
                    format!("in type `{}`, pointer has a longer lifetime than \
                          the data it references",
                         ty.user_string(self.tcx)).as_slice());
                note_and_explain_region(
                    self.tcx,
                    "the pointer is valid for ",
                    sub,
                    "");
                note_and_explain_region(
                    self.tcx,
                    "but the referenced data is only valid for ",
                    sup,
                    "");
            }
        }
    }

    fn report_sub_sup_conflict(&self,
                               var_origin: RegionVariableOrigin,
                               sub_origin: SubregionOrigin,
                               sub_region: Region,
                               sup_origin: SubregionOrigin,
                               sup_region: Region) {
        self.report_inference_failure(var_origin);

        note_and_explain_region(
            self.tcx,
            "first, the lifetime cannot outlive ",
            sup_region,
            "...");

        self.note_region_origin(sup_origin);

        note_and_explain_region(
            self.tcx,
            "but, the lifetime must be valid for ",
            sub_region,
            "...");

        self.note_region_origin(sub_origin);
    }

    fn report_sup_sup_conflict(&self,
                               var_origin: RegionVariableOrigin,
                               origin1: SubregionOrigin,
                               region1: Region,
                               origin2: SubregionOrigin,
                               region2: Region) {
        self.report_inference_failure(var_origin);

        note_and_explain_region(
            self.tcx,
            "first, the lifetime must be contained by ",
            region1,
            "...");

        self.note_region_origin(origin1);

        note_and_explain_region(
            self.tcx,
            "but, the lifetime must also be contained by ",
            region2,
            "...");

        self.note_region_origin(origin2);
    }

    fn report_processed_errors(&self,
                               var_origins: &[RegionVariableOrigin],
                               trace_origins: &[(TypeTrace, ty::type_err)],
                               same_regions: &[SameRegions]) {
        self.give_suggestion(same_regions);
        for vo in var_origins.iter() {
            self.report_inference_failure(vo.clone());
        }
        for &(ref trace, terr) in trace_origins.iter() {
            self.report_type_error(trace.clone(), &terr);
        }
    }

    fn give_suggestion(&self, same_regions: &[SameRegions]) {
        let scope_id = same_regions[0].scope_id;
        let parent = self.tcx.map.get_parent(scope_id);
        let parent_node = self.tcx.map.find(parent);
        let node_inner = match parent_node {
            Some(ref node) => match *node {
                ast_map::NodeItem(ref item) => {
                    match item.node {
                        ast::ItemFn(ref fn_decl, ref pur, _, ref gen, _) => {
                            Some((fn_decl, gen, *pur, item.ident, None, item.span))
                        },
                        _ => None
                    }
                }
                ast_map::NodeMethod(ref m) => {
                    Some((&m.decl, &m.generics, m.fn_style,
                          m.ident, Some(m.explicit_self.node), m.span))
                },
                _ => None
            },
            None => None
        };
        let (fn_decl, generics, fn_style, ident, expl_self, span)
                                    = node_inner.expect("expect item fn");
        let taken = lifetimes_in_scope(self.tcx, scope_id);
        let life_giver = LifeGiver::with_taken(taken.as_slice());
        let rebuilder = Rebuilder::new(self.tcx, *fn_decl, expl_self,
                                       generics, same_regions, &life_giver);
        let (fn_decl, expl_self, generics) = rebuilder.rebuild();
        self.give_expl_lifetime_param(&fn_decl, fn_style, ident,
                                      expl_self, &generics, span);
    }
}

struct RebuildPathInfo<'a> {
    path: &'a ast::Path,
    // indexes to insert lifetime on path.lifetimes
    indexes: Vec<uint>,
    // number of lifetimes we expect to see on the type referred by `path`
    // (e.g., expected=1 for struct Foo<'a>)
    expected: uint,
    anon_nums: &'a HashSet<uint>,
    region_names: &'a HashSet<ast::Name>
}

struct Rebuilder<'a> {
    tcx: &'a ty::ctxt,
    fn_decl: ast::P<ast::FnDecl>,
    expl_self_opt: Option<ast::ExplicitSelf_>,
    generics: &'a ast::Generics,
    same_regions: &'a [SameRegions],
    life_giver: &'a LifeGiver,
    cur_anon: Cell<uint>,
    inserted_anons: RefCell<HashSet<uint>>,
}

enum FreshOrKept {
    Fresh,
    Kept
}

impl<'a> Rebuilder<'a> {
    fn new(tcx: &'a ty::ctxt,
           fn_decl: ast::P<ast::FnDecl>,
           expl_self_opt: Option<ast::ExplicitSelf_>,
           generics: &'a ast::Generics,
           same_regions: &'a [SameRegions],
           life_giver: &'a LifeGiver)
           -> Rebuilder<'a> {
        Rebuilder {
            tcx: tcx,
            fn_decl: fn_decl,
            expl_self_opt: expl_self_opt,
            generics: generics,
            same_regions: same_regions,
            life_giver: life_giver,
            cur_anon: Cell::new(0),
            inserted_anons: RefCell::new(HashSet::new()),
        }
    }

    fn rebuild(&self)
               -> (ast::FnDecl, Option<ast::ExplicitSelf_>, ast::Generics) {
        let mut expl_self_opt = self.expl_self_opt;
        let mut inputs = self.fn_decl.inputs.clone();
        let mut output = self.fn_decl.output;
        let mut ty_params = self.generics.ty_params.clone();
        let mut kept_lifetimes = HashSet::new();
        for sr in self.same_regions.iter() {
            self.cur_anon.set(0);
            self.offset_cur_anon();
            let (anon_nums, region_names) =
                                self.extract_anon_nums_and_names(sr);
            let (lifetime, fresh_or_kept) = self.pick_lifetime(&region_names);
            match fresh_or_kept {
                Kept => { kept_lifetimes.insert(lifetime.name); }
                _ => ()
            }
            expl_self_opt = self.rebuild_expl_self(expl_self_opt, lifetime,
                                                   &anon_nums, &region_names);
            inputs = self.rebuild_args_ty(inputs.as_slice(), lifetime,
                                          &anon_nums, &region_names);
            output = self.rebuild_arg_ty_or_output(output, lifetime,
                                                   &anon_nums, &region_names);
            ty_params = self.rebuild_ty_params(ty_params, lifetime,
                                               &region_names);
        }
        let fresh_lifetimes = self.life_giver.get_generated_lifetimes();
        let all_region_names = self.extract_all_region_names();
        let generics = self.rebuild_generics(self.generics,
                                             &fresh_lifetimes,
                                             &kept_lifetimes,
                                             &all_region_names,
                                             ty_params);
        let new_fn_decl = ast::FnDecl {
            inputs: inputs,
            output: output,
            cf: self.fn_decl.cf,
            variadic: self.fn_decl.variadic
        };
        (new_fn_decl, expl_self_opt, generics)
    }

    fn pick_lifetime(&self,
                     region_names: &HashSet<ast::Name>)
                     -> (ast::Lifetime, FreshOrKept) {
        if region_names.len() > 0 {
            // It's not necessary to convert the set of region names to a
            // vector of string and then sort them. However, it makes the
            // choice of lifetime name deterministic and thus easier to test.
            let mut names = Vec::new();
            for rn in region_names.iter() {
                let lt_name = token::get_name(*rn).get().to_string();
                names.push(lt_name);
            }
            names.sort();
            let name = token::str_to_ident(names.get(0).as_slice()).name;
            return (name_to_dummy_lifetime(name), Kept);
        }
        return (self.life_giver.give_lifetime(), Fresh);
    }

    fn extract_anon_nums_and_names(&self, same_regions: &SameRegions)
                                   -> (HashSet<uint>, HashSet<ast::Name>) {
        let mut anon_nums = HashSet::new();
        let mut region_names = HashSet::new();
        for br in same_regions.regions.iter() {
            match *br {
                ty::BrAnon(i) => {
                    anon_nums.insert(i);
                }
                ty::BrNamed(_, name) => {
                    region_names.insert(name);
                }
                _ => ()
            }
        }
        (anon_nums, region_names)
    }

    fn extract_all_region_names(&self) -> HashSet<ast::Name> {
        let mut all_region_names = HashSet::new();
        for sr in self.same_regions.iter() {
            for br in sr.regions.iter() {
                match *br {
                    ty::BrNamed(_, name) => {
                        all_region_names.insert(name);
                    }
                    _ => ()
                }
            }
        }
        all_region_names
    }

    fn inc_cur_anon(&self, n: uint) {
        let anon = self.cur_anon.get();
        self.cur_anon.set(anon+n);
    }

    fn offset_cur_anon(&self) {
        let mut anon = self.cur_anon.get();
        while self.inserted_anons.borrow().contains(&anon) {
            anon += 1;
        }
        self.cur_anon.set(anon);
    }

    fn inc_and_offset_cur_anon(&self, n: uint) {
        self.inc_cur_anon(n);
        self.offset_cur_anon();
    }

    fn track_anon(&self, anon: uint) {
        self.inserted_anons.borrow_mut().insert(anon);
    }

    fn rebuild_ty_params(&self,
                         ty_params: OwnedSlice<ast::TyParam>,
                         lifetime: ast::Lifetime,
                         region_names: &HashSet<ast::Name>)
                         -> OwnedSlice<ast::TyParam> {
        ty_params.map(|ty_param| {
            let bounds = self.rebuild_ty_param_bounds(ty_param.bounds.clone(),
                                                      lifetime,
                                                      region_names);
            ast::TyParam {
                ident: ty_param.ident,
                id: ty_param.id,
                bounds: bounds,
                default: ty_param.default,
                span: ty_param.span,
                sized: ty_param.sized,
            }
        })
    }

    fn rebuild_ty_param_bounds(&self,
                               ty_param_bounds: OwnedSlice<ast::TyParamBound>,
                               lifetime: ast::Lifetime,
                               region_names: &HashSet<ast::Name>)
                               -> OwnedSlice<ast::TyParamBound> {
        ty_param_bounds.map(|tpb| {
            match tpb {
                &ast::StaticRegionTyParamBound => ast::StaticRegionTyParamBound,
                &ast::OtherRegionTyParamBound(s) => ast::OtherRegionTyParamBound(s),
                &ast::TraitTyParamBound(ref tr) => {
                    let last_seg = tr.path.segments.last().unwrap();
                    let mut insert = Vec::new();
                    for (i, lt) in last_seg.lifetimes.iter().enumerate() {
                        if region_names.contains(&lt.name) {
                            insert.push(i);
                        }
                    }
                    let rebuild_info = RebuildPathInfo {
                        path: &tr.path,
                        indexes: insert,
                        expected: last_seg.lifetimes.len(),
                        anon_nums: &HashSet::new(),
                        region_names: region_names
                    };
                    let new_path = self.rebuild_path(rebuild_info, lifetime);
                    ast::TraitTyParamBound(ast::TraitRef {
                        path: new_path,
                        ref_id: tr.ref_id,
                    })
                }
            }
        })
    }

    fn rebuild_expl_self(&self,
                         expl_self_opt: Option<ast::ExplicitSelf_>,
                         lifetime: ast::Lifetime,
                         anon_nums: &HashSet<uint>,
                         region_names: &HashSet<ast::Name>)
                         -> Option<ast::ExplicitSelf_> {
        match expl_self_opt {
            Some(expl_self) => match expl_self {
                ast::SelfRegion(lt_opt, muta) => match lt_opt {
                    Some(lt) => if region_names.contains(&lt.name) {
                        return Some(ast::SelfRegion(Some(lifetime), muta));
                    },
                    None => {
                        let anon = self.cur_anon.get();
                        self.inc_and_offset_cur_anon(1);
                        if anon_nums.contains(&anon) {
                            self.track_anon(anon);
                            return Some(ast::SelfRegion(Some(lifetime), muta));
                        }
                    }
                },
                _ => ()
            },
            None => ()
        }
        expl_self_opt
    }

    fn rebuild_generics(&self,
                        generics: &ast::Generics,
                        add: &Vec<ast::Lifetime>,
                        keep: &HashSet<ast::Name>,
                        remove: &HashSet<ast::Name>,
                        ty_params: OwnedSlice<ast::TyParam>)
                        -> ast::Generics {
        let mut lifetimes = Vec::new();
        for lt in add.iter() {
            lifetimes.push(*lt);
        }
        for lt in generics.lifetimes.iter() {
            if keep.contains(&lt.name) || !remove.contains(&lt.name) {
                lifetimes.push((*lt).clone());
            }
        }
        ast::Generics {
            lifetimes: lifetimes,
            ty_params: ty_params
        }
    }

    fn rebuild_args_ty(&self,
                       inputs: &[ast::Arg],
                       lifetime: ast::Lifetime,
                       anon_nums: &HashSet<uint>,
                       region_names: &HashSet<ast::Name>)
                       -> Vec<ast::Arg> {
        let mut new_inputs = Vec::new();
        for arg in inputs.iter() {
            let new_ty = self.rebuild_arg_ty_or_output(arg.ty, lifetime,
                                                       anon_nums, region_names);
            let possibly_new_arg = ast::Arg {
                ty: new_ty,
                pat: arg.pat,
                id: arg.id
            };
            new_inputs.push(possibly_new_arg);
        }
        new_inputs
    }

    fn rebuild_arg_ty_or_output(&self,
                                ty: ast::P<ast::Ty>,
                                lifetime: ast::Lifetime,
                                anon_nums: &HashSet<uint>,
                                region_names: &HashSet<ast::Name>)
                                -> ast::P<ast::Ty> {
        let mut new_ty = ty;
        let mut ty_queue = vec!(ty);
        let mut cur_ty;
        while !ty_queue.is_empty() {
            cur_ty = ty_queue.shift().unwrap();
            match cur_ty.node {
                ast::TyRptr(lt_opt, mut_ty) => {
                    match lt_opt {
                        Some(lt) => if region_names.contains(&lt.name) {
                            new_ty = self.rebuild_ty(new_ty, cur_ty,
                                                     lifetime, None);
                        },
                        None => {
                            let anon = self.cur_anon.get();
                            if anon_nums.contains(&anon) {
                                new_ty = self.rebuild_ty(new_ty, cur_ty,
                                                         lifetime, None);
                                self.track_anon(anon);
                            }
                            self.inc_and_offset_cur_anon(1);
                        }
                    }
                    ty_queue.push(mut_ty.ty);
                }
                ast::TyPath(ref path, _, id) => {
                    let a_def = match self.tcx.def_map.borrow().find(&id) {
                        None => {
                            self.tcx
                                .sess
                                .fatal(format!(
                                        "unbound path {}",
                                        pprust::path_to_str(path)).as_slice())
                        }
                        Some(&d) => d
                    };
                    match a_def {
                        ast::DefTy(did) | ast::DefStruct(did) => {
                            let ty::ty_param_bounds_and_ty {
                                generics: generics,
                                ty: _
                            } = ty::lookup_item_type(self.tcx, did);

                            let expected = generics.region_param_defs().len();
                            let lifetimes = &path.segments.last()
                                                 .unwrap().lifetimes;
                            let mut insert = Vec::new();
                            if lifetimes.len() == 0 {
                                let anon = self.cur_anon.get();
                                for (i, a) in range(anon,
                                                    anon+expected).enumerate() {
                                    if anon_nums.contains(&a) {
                                        insert.push(i);
                                    }
                                    self.track_anon(a);
                                }
                                self.inc_and_offset_cur_anon(expected);
                            } else {
                                for (i, lt) in lifetimes.iter().enumerate() {
                                    if region_names.contains(&lt.name) {
                                        insert.push(i);
                                    }
                                }
                            }
                            let rebuild_info = RebuildPathInfo {
                                path: path,
                                indexes: insert,
                                expected: expected,
                                anon_nums: anon_nums,
                                region_names: region_names
                            };
                            new_ty = self.rebuild_ty(new_ty, cur_ty,
                                                     lifetime,
                                                     Some(rebuild_info));
                        }
                        _ => ()
                    }

                }
                _ => ty_queue.push_all_move(ast_util::get_inner_tys(cur_ty))
            }
        }
        new_ty
    }

    fn rebuild_ty(&self,
                  from: ast::P<ast::Ty>,
                  to: ast::P<ast::Ty>,
                  lifetime: ast::Lifetime,
                  rebuild_path_info: Option<RebuildPathInfo>)
                  -> ast::P<ast::Ty> {

        fn build_to(from: ast::P<ast::Ty>,
                    to: ast::P<ast::Ty>)
                    -> ast::P<ast::Ty> {
            if from.id == to.id {
                return to;
            }
            let new_node = match from.node {
                ast::TyRptr(ref lifetime, ref mut_ty) => {
                    let new_mut_ty = ast::MutTy {
                        ty: build_to(mut_ty.ty, to),
                        mutbl: mut_ty.mutbl
                    };
                    ast::TyRptr(*lifetime, new_mut_ty)
                }
                ast::TyPtr(ref mut_ty) => {
                    let new_mut_ty = ast::MutTy {
                        ty: build_to(mut_ty.ty, to),
                        mutbl: mut_ty.mutbl
                    };
                    ast::TyPtr(new_mut_ty)
                }
                ast::TyBox(ref ty) => ast::TyBox(build_to(*ty, to)),
                ast::TyVec(ref ty) => ast::TyVec(build_to(*ty, to)),
                ast::TyUniq(ref ty) => ast::TyUniq(build_to(*ty, to)),
                ast::TyFixedLengthVec(ref ty, ref e) => {
                    ast::TyFixedLengthVec(build_to(*ty, to), *e)
                }
                ast::TyTup(ref tys) => {
                    let mut new_tys = Vec::new();
                    for ty in tys.iter() {
                        new_tys.push(build_to(*ty, to));
                    }
                    ast::TyTup(new_tys)
                }
                ref other => other.clone()
            };
            @ast::Ty { id: from.id, node: new_node, span: from.span }
        }

        let new_ty_node = match to.node {
            ast::TyRptr(_, mut_ty) => ast::TyRptr(Some(lifetime), mut_ty),
            ast::TyPath(_, ref bounds, id) => {
                let rebuild_info = match rebuild_path_info {
                    Some(ri) => ri,
                    None => fail!("expect index_opt in rebuild_ty/ast::TyPath")
                };
                let new_path = self.rebuild_path(rebuild_info, lifetime);
                ast::TyPath(new_path, bounds.clone(), id)
            }
            _ => fail!("expect ast::TyRptr or ast::TyPath")
        };
        let new_ty = @ast::Ty {
            id: to.id,
            node: new_ty_node,
            span: to.span
        };
        build_to(from, new_ty)
    }

    fn rebuild_path(&self,
                    rebuild_info: RebuildPathInfo,
                    lifetime: ast::Lifetime)
                    -> ast::Path {
        let RebuildPathInfo {
            path: path,
            indexes: indexes,
            expected: expected,
            anon_nums: anon_nums,
            region_names: region_names,
        } = rebuild_info;

        let last_seg = path.segments.last().unwrap();
        let mut new_lts = Vec::new();
        if last_seg.lifetimes.len() == 0 {
            // traverse once to see if there's a need to insert lifetime
            let need_insert = range(0, expected).any(|i| {
                indexes.contains(&i)
            });
            if need_insert {
                for i in range(0, expected) {
                    if indexes.contains(&i) {
                        new_lts.push(lifetime);
                    } else {
                        new_lts.push(self.life_giver.give_lifetime());
                    }
                }
            }
        } else {
            for (i, lt) in last_seg.lifetimes.iter().enumerate() {
                if indexes.contains(&i) {
                    new_lts.push(lifetime);
                } else {
                    new_lts.push(*lt);
                }
            }
        }
        let new_types = last_seg.types.map(|&t| {
            self.rebuild_arg_ty_or_output(t, lifetime, anon_nums, region_names)
        });
        let new_seg = ast::PathSegment {
            identifier: last_seg.identifier,
            lifetimes: new_lts,
            types: new_types,
        };
        let mut new_segs = Vec::new();
        new_segs.push_all(path.segments.init());
        new_segs.push(new_seg);
        ast::Path {
            span: path.span,
            global: path.global,
            segments: new_segs
        }
    }
}

impl<'a> ErrorReportingHelpers for InferCtxt<'a> {
    fn give_expl_lifetime_param(&self,
                                decl: &ast::FnDecl,
                                fn_style: ast::FnStyle,
                                ident: ast::Ident,
                                opt_explicit_self: Option<ast::ExplicitSelf_>,
                                generics: &ast::Generics,
                                span: codemap::Span) {
        let suggested_fn = pprust::fun_to_str(decl, fn_style, ident,
                                              opt_explicit_self, generics);
        let msg = format!("consider using an explicit lifetime \
                           parameter as shown: {}", suggested_fn);
        self.tcx.sess.span_note(span, msg.as_slice());
    }

    fn report_inference_failure(&self,
                                var_origin: RegionVariableOrigin) {
        let var_description = match var_origin {
            infer::MiscVariable(_) => "".to_string(),
            infer::PatternRegion(_) => " for pattern".to_string(),
            infer::AddrOfRegion(_) => " for borrow expression".to_string(),
            infer::AddrOfSlice(_) => " for slice expression".to_string(),
            infer::Autoref(_) => " for autoref".to_string(),
            infer::Coercion(_) => " for automatic coercion".to_string(),
            infer::LateBoundRegion(_, br) => {
                format!(" for {}in function call",
                        bound_region_to_str(self.tcx, "lifetime parameter ", true, br))
            }
            infer::BoundRegionInFnType(_, br) => {
                format!(" for {}in function type",
                        bound_region_to_str(self.tcx, "lifetime parameter ", true, br))
            }
            infer::EarlyBoundRegion(_, name) => {
                format!(" for lifetime parameter `{}",
                        token::get_name(name).get())
            }
            infer::BoundRegionInCoherence(name) => {
                format!(" for lifetime parameter `{} in coherence check",
                        token::get_name(name).get())
            }
            infer::UpvarRegion(ref upvar_id, _) => {
                format!(" for capture of `{}` by closure",
                        ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_str())
            }
        };

        self.tcx.sess.span_err(
            var_origin.span(),
            format!("cannot infer an appropriate lifetime{} \
                    due to conflicting requirements",
                    var_description).as_slice());
    }

    fn note_region_origin(&self, origin: SubregionOrigin) {
        match origin {
            infer::Subtype(ref trace) => {
                let desc = match trace.origin {
                    infer::Misc(_) => {
                        format!("types are compatible")
                    }
                    infer::MethodCompatCheck(_) => {
                        format!("method type is compatible with trait")
                    }
                    infer::ExprAssignable(_) => {
                        format!("expression is assignable")
                    }
                    infer::RelateTraitRefs(_) => {
                        format!("traits are compatible")
                    }
                    infer::RelateSelfType(_) => {
                        format!("type matches impl")
                    }
                    infer::MatchExpressionArm(_, _) => {
                        format!("match arms have compatible types")
                    }
                    infer::IfExpression(_) => {
                        format!("if and else have compatible types")
                    }
                };

                match self.values_str(&trace.values) {
                    Some(values_str) => {
                        self.tcx.sess.span_note(
                            trace.origin.span(),
                            format!("...so that {} ({})",
                                    desc, values_str).as_slice());
                    }
                    None => {
                        // Really should avoid printing this error at
                        // all, since it is derived, but that would
                        // require more refactoring than I feel like
                        // doing right now. - nmatsakis
                        self.tcx.sess.span_note(
                            trace.origin.span(),
                            format!("...so that {}", desc).as_slice());
                    }
                }
            }
            infer::Reborrow(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that reference does not outlive \
                    borrowed content");
            }
            infer::ReborrowUpvar(span, ref upvar_id) => {
                self.tcx.sess.span_note(
                    span,
                    format!(
                        "...so that closure can access `{}`",
                        ty::local_var_name_str(self.tcx, upvar_id.var_id)
                            .get()
                            .to_str()).as_slice())
            }
            infer::InfStackClosure(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that closure does not outlive its stack frame");
            }
            infer::InvokeClosure(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that closure is not invoked outside its lifetime");
            }
            infer::DerefPointer(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that pointer is not dereferenced \
                    outside its lifetime");
            }
            infer::FreeVariable(span, id) => {
                self.tcx.sess.span_note(
                    span,
                    format!("...so that captured variable `{}` \
                            does not outlive the enclosing closure",
                            ty::local_var_name_str(
                                self.tcx,
                                id).get().to_str()).as_slice());
            }
            infer::IndexSlice(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that slice is not indexed outside the lifetime");
            }
            infer::RelateObjectBound(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that source pointer does not outlive \
                     lifetime bound of the object type");
            }
            infer::CallRcvr(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that method receiver is valid for the method call");
            }
            infer::CallArg(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that argument is valid for the call");
            }
            infer::CallReturn(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that return value is valid for the call");
            }
            infer::AddrOf(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that reference is valid \
                     at the time of borrow");
            }
            infer::AutoBorrow(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that automatically reference is valid \
                     at the time of borrow");
            }
            infer::BindingTypeIsNotValidAtDecl(span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that variable is valid at time of its declaration");
            }
            infer::ReferenceOutlivesReferent(_, span) => {
                self.tcx.sess.span_note(
                    span,
                    "...so that the pointer does not outlive the \
                    data it points at");
            }
        }
    }
}

trait Resolvable {
    fn resolve(&self, infcx: &InferCtxt) -> Self;
    fn contains_error(&self) -> bool;
}

impl Resolvable for ty::t {
    fn resolve(&self, infcx: &InferCtxt) -> ty::t {
        infcx.resolve_type_vars_if_possible(*self)
    }
    fn contains_error(&self) -> bool {
        ty::type_is_error(*self)
    }
}

impl Resolvable for Rc<ty::TraitRef> {
    fn resolve(&self, infcx: &InferCtxt) -> Rc<ty::TraitRef> {
        Rc::new(infcx.resolve_type_vars_in_trait_ref_if_possible(&**self))
    }
    fn contains_error(&self) -> bool {
        ty::trait_ref_contains_error(&**self)
    }
}

fn lifetimes_in_scope(tcx: &ty::ctxt,
                      scope_id: ast::NodeId)
                      -> Vec<ast::Lifetime> {
    let mut taken = Vec::new();
    let parent = tcx.map.get_parent(scope_id);
    let method_id_opt = match tcx.map.find(parent) {
        Some(node) => match node {
            ast_map::NodeItem(item) => match item.node {
                ast::ItemFn(_, _, _, ref gen, _) => {
                    taken.push_all(gen.lifetimes.as_slice());
                    None
                },
                _ => None
            },
            ast_map::NodeMethod(m) => {
                taken.push_all(m.generics.lifetimes.as_slice());
                Some(m.id)
            },
            _ => None
        },
        None => None
    };
    if method_id_opt.is_some() {
        let method_id = method_id_opt.unwrap();
        let parent = tcx.map.get_parent(method_id);
        match tcx.map.find(parent) {
            Some(node) => match node {
                ast_map::NodeItem(item) => match item.node {
                    ast::ItemImpl(ref gen, _, _, _) => {
                        taken.push_all(gen.lifetimes.as_slice());
                    }
                    _ => ()
                },
                _ => ()
            },
            None => ()
        }
    }
    return taken;
}

// LifeGiver is responsible for generating fresh lifetime names
struct LifeGiver {
    taken: HashSet<String>,
    counter: Cell<uint>,
    generated: RefCell<Vec<ast::Lifetime>>,
}

impl LifeGiver {
    fn with_taken(taken: &[ast::Lifetime]) -> LifeGiver {
        let mut taken_ = HashSet::new();
        for lt in taken.iter() {
            let lt_name = token::get_name(lt.name).get().to_string();
            taken_.insert(lt_name);
        }
        LifeGiver {
            taken: taken_,
            counter: Cell::new(0),
            generated: RefCell::new(Vec::new()),
        }
    }

    fn inc_counter(&self) {
        let c = self.counter.get();
        self.counter.set(c+1);
    }

    fn give_lifetime(&self) -> ast::Lifetime {
        let mut lifetime;
        loop {
            let s = num_to_str(self.counter.get());
            if !self.taken.contains(&s) {
                lifetime = name_to_dummy_lifetime(
                                    token::str_to_ident(s.as_slice()).name);
                self.generated.borrow_mut().push(lifetime);
                break;
            }
            self.inc_counter();
        }
        self.inc_counter();
        return lifetime;

        // 0 .. 25 generates a .. z, 26 .. 51 generates aa .. zz, and so on
        fn num_to_str(counter: uint) -> String {
            let mut s = String::new();
            let (n, r) = (counter/26 + 1, counter % 26);
            let letter: char = from_u32((r+97) as u32).unwrap();
            for _ in range(0, n) {
                s.push_char(letter);
            }
            s
        }
    }

    fn get_generated_lifetimes(&self) -> Vec<ast::Lifetime> {
        self.generated.borrow().clone()
    }
}