<commit_before>use std::collections::HashMap;
use std::fmt;
use syntax::{Expr, ExprF, Literal};
use typed_arena::Arena;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Error<'str, 'ty> {
  Unify(&'ty Ty<'ty>, &'ty Ty<'ty>),
  Var(&'str str),
}

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct ID(usize);

#[derive(Clone, Debug, Eq, PartialEq)]
pub enum Ty<'ty> {
  Deferred(ID),
  Func(&'ty Ty<'ty>, &'ty Ty<'ty>),
  Bool,
  Int,
  Str,
  Bytes,
  Tuple(Vec<&'ty Ty<'ty>>),
}

pub static TY_BOOL:  Ty<'static> = Ty::Bool;
pub static TY_INT:   Ty<'static> = Ty::Int;
pub static TY_STR:   Ty<'static> = Ty::Str;
pub static TY_BYTES: Ty<'static> = Ty::Bytes;

impl<'ty> Ty<'ty> {
  pub fn pretty<Purge, W>(&'ty self, purge: &Purge, into: &mut W) -> fmt::Result
    where
      Purge: Fn(&'ty Ty<'ty>) -> &'ty Ty<'ty>,
      W: fmt::Write {
    match *purge(self) {
      Ty::Deferred(ID(id)) =>
        write!(into, "t{}", id),
      Ty::Func(a, b) => {
        try!(write!(into, "("));
        try!(a.pretty(purge, into));
        try!(write!(into, " -> "));
        try!(b.pretty(purge, into));
        try!(write!(into, ")"));
        Ok(())
      },
      Ty::Bool =>
        write!(into, "bool"),
      Ty::Int =>
        write!(into, "int"),
      Ty::Str =>
        write!(into, "str"),
      Ty::Bytes =>
        write!(into, "bytes"),
      Ty::Tuple(ref elem_tys) => {
        try!(write!(into, "{{"));
        for elem_ty in elem_tys {
          try!(elem_ty.pretty(purge, into));
          try!(write!(into, ","));
        }
        try!(write!(into, "}}"));
        Ok(())
      },
    }
  }

  pub fn pretty_string<Purge>(&'ty self, purge: &Purge) -> String
    where Purge: Fn(&'ty Ty<'ty>) -> &'ty Ty<'ty> {
    let mut pretty = String::new();
    self.pretty(purge, &mut pretty).unwrap();
    pretty
  }
}

pub struct Check<'ty> {
  arena: &'ty Arena<Ty<'ty>>,
  next_id: usize,
  solved: HashMap<ID, &'ty Ty<'ty>>,
}

impl<'ty> Check<'ty> {
  pub fn new(arena: &'ty Arena<Ty<'ty>>) -> Self {
    Check{
      arena: arena,
      next_id: 0,
      solved: HashMap::new(),
    }
  }

  pub fn fresh(&mut self) -> &'ty Ty<'ty> {
    let ty = self.arena.alloc(Ty::Deferred(ID(self.next_id)));
    self.next_id += 1;
    ty
  }

  fn solve(&mut self, id: ID, ty: &'ty Ty<'ty>) {
    self.solved.insert(id, ty);
  }

  pub fn purge(&self, ty: &'ty Ty<'ty>) -> &'ty Ty<'ty> {
    match ty {
      &Ty::Deferred(id) =>
        match self.solved.get(&id) {
          Some(uy) => self.purge(uy),
          None => ty,
        },
      _ => ty,
    }
  }

  pub fn unify<'str>(&mut self, ty: &'ty Ty<'ty>, uy: &'ty Ty<'ty>)
    -> Result<(), Error<'str, 'ty>> {
    match (self.purge(ty), self.purge(uy)) {
      (&Ty::Deferred(ty_id), &Ty::Deferred(uy_id))
        if ty_id == uy_id =>
        Ok(()),
      (&Ty::Deferred(ty_id), uy_p) => {
        self.solve(ty_id, uy_p);
        Ok(())
      },
      (ty_p, &Ty::Deferred(uy_id)) => {
        self.solve(uy_id, ty_p);
        Ok(())
      },
      (&Ty::Func(ty_a, ty_b), &Ty::Func(uy_a, uy_b)) => {
        try!(self.unify(ty_a, uy_a));
        try!(self.unify(ty_b, uy_b));
        Ok(())
      },
      (&Ty::Bool, &Ty::Bool) =>
        Ok(()),
      (&Ty::Int, &Ty::Int) =>
        Ok(()),
      (&Ty::Str, &Ty::Str) =>
        Ok(()),
      (&Ty::Bytes, &Ty::Bytes) =>
        Ok(()),
      (a, b) => {<commit_msg>Add unification for tuple types<commit_after>use std::collections::HashMap;
use std::fmt;
use syntax::{Expr, ExprF, Literal};
use typed_arena::Arena;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Error<'str, 'ty> {
  Unify(&'ty Ty<'ty>, &'ty Ty<'ty>),
  Var(&'str str),
}

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct ID(usize);

#[derive(Clone, Debug, Eq, PartialEq)]
pub enum Ty<'ty> {
  Deferred(ID),
  Func(&'ty Ty<'ty>, &'ty Ty<'ty>),
  Bool,
  Int,
  Str,
  Bytes,
  Tuple(Vec<&'ty Ty<'ty>>),
}

pub static TY_BOOL:  Ty<'static> = Ty::Bool;
pub static TY_INT:   Ty<'static> = Ty::Int;
pub static TY_STR:   Ty<'static> = Ty::Str;
pub static TY_BYTES: Ty<'static> = Ty::Bytes;

impl<'ty> Ty<'ty> {
  pub fn pretty<Purge, W>(&'ty self, purge: &Purge, into: &mut W) -> fmt::Result
    where
      Purge: Fn(&'ty Ty<'ty>) -> &'ty Ty<'ty>,
      W: fmt::Write {
    match *purge(self) {
      Ty::Deferred(ID(id)) =>
        write!(into, "t{}", id),
      Ty::Func(a, b) => {
        try!(write!(into, "("));
        try!(a.pretty(purge, into));
        try!(write!(into, " -> "));
        try!(b.pretty(purge, into));
        try!(write!(into, ")"));
        Ok(())
      },
      Ty::Bool =>
        write!(into, "bool"),
      Ty::Int =>
        write!(into, "int"),
      Ty::Str =>
        write!(into, "str"),
      Ty::Bytes =>
        write!(into, "bytes"),
      Ty::Tuple(ref elem_tys) => {
        try!(write!(into, "{{"));
        for elem_ty in elem_tys {
          try!(elem_ty.pretty(purge, into));
          try!(write!(into, ","));
        }
        try!(write!(into, "}}"));
        Ok(())
      },
    }
  }

  pub fn pretty_string<Purge>(&'ty self, purge: &Purge) -> String
    where Purge: Fn(&'ty Ty<'ty>) -> &'ty Ty<'ty> {
    let mut pretty = String::new();
    self.pretty(purge, &mut pretty).unwrap();
    pretty
  }
}

pub struct Check<'ty> {
  arena: &'ty Arena<Ty<'ty>>,
  next_id: usize,
  solved: HashMap<ID, &'ty Ty<'ty>>,
}

impl<'ty> Check<'ty> {
  pub fn new(arena: &'ty Arena<Ty<'ty>>) -> Self {
    Check{
      arena: arena,
      next_id: 0,
      solved: HashMap::new(),
    }
  }

  pub fn fresh(&mut self) -> &'ty Ty<'ty> {
    let ty = self.arena.alloc(Ty::Deferred(ID(self.next_id)));
    self.next_id += 1;
    ty
  }

  fn solve(&mut self, id: ID, ty: &'ty Ty<'ty>) {
    self.solved.insert(id, ty);
  }

  pub fn purge(&self, ty: &'ty Ty<'ty>) -> &'ty Ty<'ty> {
    match ty {
      &Ty::Deferred(id) =>
        match self.solved.get(&id) {
          Some(uy) => self.purge(uy),
          None => ty,
        },
      _ => ty,
    }
  }

  pub fn unify<'str>(&mut self, ty: &'ty Ty<'ty>, uy: &'ty Ty<'ty>)
    -> Result<(), Error<'str, 'ty>> {
    match (self.purge(ty), self.purge(uy)) {
      (&Ty::Deferred(ty_id), &Ty::Deferred(uy_id))
        if ty_id == uy_id =>
        Ok(()),
      (&Ty::Deferred(ty_id), uy_p) => {
        self.solve(ty_id, uy_p);
        Ok(())
      },
      (ty_p, &Ty::Deferred(uy_id)) => {
        self.solve(uy_id, ty_p);
        Ok(())
      },
      (&Ty::Func(ty_a, ty_b), &Ty::Func(uy_a, uy_b)) => {
        try!(self.unify(ty_a, uy_a));
        try!(self.unify(ty_b, uy_b));
        Ok(())
      },
      (&Ty::Bool, &Ty::Bool) =>
        Ok(()),
      (&Ty::Int, &Ty::Int) =>
        Ok(()),
      (&Ty::Str, &Ty::Str) =>
        Ok(()),
      (&Ty::Bytes, &Ty::Bytes) =>
        Ok(()),
      (&Ty::Tuple(ref elem_tys), &Ty::Tuple(ref elem_uys)) => {
        if elem_tys.len() != elem_uys.len() {
          Err(Error::Unify(&TY_BOOL, &TY_INT)) // FIXME: Tuple types.
        } else {
          for (ty, uy) in elem_tys.iter().zip(elem_uys.iter()) {
            try!(self.unify(ty, uy));
          }
          Ok(())
        }
      },
      (a, b) => {
{'fraction_non_alphanumeric': 0.2324256737982773, 'fraction_numerical': 0.0005557099194220616, 'mean_word_length': 2.421577946768061, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 138, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3544243', 'n_tokens_mistral': 2880, 'n_tokens_neox': 2932, 'n_words': 581}