src/librustc/middle/subst.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 // Type substitutions.
  12
  13 use middle::ty;
  14 use middle::ty_fold;
  15 use middle::ty_fold::{TypeFoldable, TypeFolder};
  16 use util::ppaux::Repr;
  17
  18 use std::fmt;
  19 use std::mem;
  20 use std::raw;
  21 use std::slice::{Items, MutItems};
  22 use std::vec::Vec;
  23 use syntax::codemap::{Span, DUMMY_SP};
  24
  25 ///////////////////////////////////////////////////////////////////////////
  26 // HomogeneousTuple3 trait
  27 //
  28 // This could be moved into standard library at some point.
  29
  30 trait HomogeneousTuple3<T> {
  31     fn len(&self) -> uint;
  32     fn as_slice<'a>(&'a self) -> &'a [T];
  33     fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T];
  34     fn iter<'a>(&'a self) -> Items<'a, T>;
  35     fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T>;
  36     fn get<'a>(&'a self, index: uint) -> Option<&'a T>;
  37     fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T>;
  38 }
  39
  40 impl<T> HomogeneousTuple3<T> for (T, T, T) {
  41     fn len(&self) -> uint {
  42         3
  43     }
  44
  45     fn as_slice<'a>(&'a self) -> &'a [T] {
  46         unsafe {
  47             let ptr: *const T = mem::transmute(self);
  48             let slice = raw::Slice { data: ptr, len: 3 };
  49             mem::transmute(slice)
  50         }
  51     }
  52
  53     fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
  54         unsafe {
  55             let ptr: *const T = mem::transmute(self);
  56             let slice = raw::Slice { data: ptr, len: 3 };
  57             mem::transmute(slice)
  58         }
  59     }
  60
  61     fn iter<'a>(&'a self) -> Items<'a, T> {
  62         let slice: &'a [T] = self.as_slice();
  63         slice.iter()
  64     }
  65
  66     fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
  67         self.as_mut_slice().mut_iter()
  68     }
  69
  70     fn get<'a>(&'a self, index: uint) -> Option<&'a T> {
  71         self.as_slice().get(index)
  72     }
  73
  74     fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T> {
  75         Some(&mut self.as_mut_slice()[index]) // wrong: fallible
  76     }
  77 }
  78
  79 ///////////////////////////////////////////////////////////////////////////
  80
  81 /**
  82  * A substitution mapping type/region parameters to new values. We
  83  * identify each in-scope parameter by an *index* and a *parameter
  84  * space* (which indices where the parameter is defined; see
  85  * `ParamSpace`).
  86  */
  87 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
  88 pub struct Substs {
  89     pub types: VecPerParamSpace<ty::t>,
  90     pub regions: RegionSubsts,
  91 }
  92
  93 /**
  94  * Represents the values to use when substituting lifetime parameters.
  95  * If the value is `ErasedRegions`, then this subst is occurring during
  96  * trans, and all region parameters will be replaced with `ty::ReStatic`. */
  97 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
  98 pub enum RegionSubsts {
  99     ErasedRegions,
 100     NonerasedRegions(VecPerParamSpace<ty::Region>)
 101 }
 102
 103 impl Substs {
 104     pub fn new(t: VecPerParamSpace<ty::t>,
 105                r: VecPerParamSpace<ty::Region>)
 106                -> Substs
 107     {
 108         Substs { types: t, regions: NonerasedRegions(r) }
 109     }
 110
 111     pub fn new_type(t: Vec<ty::t>,
 112                     r: Vec<ty::Region>)
 113                     -> Substs
 114     {
 115         Substs::new(VecPerParamSpace::new(t, Vec::new(), Vec::new()),
 116                     VecPerParamSpace::new(r, Vec::new(), Vec::new()))
 117     }
 118
 119     pub fn new_trait(t: Vec<ty::t>,
 120                      r: Vec<ty::Region>,
 121                      s: ty::t)
 122                     -> Substs
 123     {
 124         Substs::new(VecPerParamSpace::new(t, vec!(s), Vec::new()),
 125                     VecPerParamSpace::new(r, Vec::new(), Vec::new()))
 126     }
 127
 128     pub fn erased(t: VecPerParamSpace<ty::t>) -> Substs
 129     {
 130         Substs { types: t, regions: ErasedRegions }
 131     }
 132
 133     pub fn empty() -> Substs {
 134         Substs {
 135             types: VecPerParamSpace::empty(),
 136             regions: NonerasedRegions(VecPerParamSpace::empty()),
 137         }
 138     }
 139
 140     pub fn trans_empty() -> Substs {
 141         Substs {
 142             types: VecPerParamSpace::empty(),
 143             regions: ErasedRegions
 144         }
 145     }
 146
 147     pub fn is_noop(&self) -> bool {
 148         let regions_is_noop = match self.regions {
 149             ErasedRegions => false, // may be used to canonicalize
 150             NonerasedRegions(ref regions) => regions.is_empty(),
 151         };
 152
 153         regions_is_noop && self.types.is_empty()
 154     }
 155
 156     pub fn self_ty(&self) -> Option<ty::t> {
 157         self.types.get_self().map(|&t| t)
 158     }
 159
 160     pub fn with_self_ty(&self, self_ty: ty::t) -> Substs {
 161         assert!(self.self_ty().is_none());
 162         let mut s = (*self).clone();
 163         s.types.push(SelfSpace, self_ty);
 164         s
 165     }
 166
 167     pub fn erase_regions(self) -> Substs {
 168         let Substs { types: types, regions: _ } = self;
 169         Substs { types: types, regions: ErasedRegions }
 170     }
 171
 172     pub fn regions<'a>(&'a self) -> &'a VecPerParamSpace<ty::Region> {
 173         /*!
 174          * Since ErasedRegions are only to be used in trans, most of
 175          * the compiler can use this method to easily access the set
 176          * of region substitutions.
 177          */
 178
 179         match self.regions {
 180             ErasedRegions => fail!("Erased regions only expected in trans"),
 181             NonerasedRegions(ref r) => r
 182         }
 183     }
 184
 185     pub fn mut_regions<'a>(&'a mut self) -> &'a mut VecPerParamSpace<ty::Region> {
 186         /*!
 187          * Since ErasedRegions are only to be used in trans, most of
 188          * the compiler can use this method to easily access the set
 189          * of region substitutions.
 190          */
 191
 192         match self.regions {
 193             ErasedRegions => fail!("Erased regions only expected in trans"),
 194             NonerasedRegions(ref mut r) => r
 195         }
 196     }
 197
 198     pub fn with_method_from(self, substs: &Substs) -> Substs {
 199         self.with_method(Vec::from_slice(substs.types.get_slice(FnSpace)),
 200                          Vec::from_slice(substs.regions().get_slice(FnSpace)))
 201     }
 202
 203     pub fn with_method(self,
 204                        m_types: Vec<ty::t>,
 205                        m_regions: Vec<ty::Region>)
 206                        -> Substs
 207     {
 208         let Substs { types, regions } = self;
 209         let types = types.with_vec(FnSpace, m_types);
 210         let regions = regions.map(m_regions,
 211                                   |r, m_regions| r.with_vec(FnSpace, m_regions));
 212         Substs { types: types, regions: regions }
 213     }
 214 }
 215
 216 impl RegionSubsts {
 217     fn map<A>(self,
 218               a: A,
 219               op: |VecPerParamSpace<ty::Region>, A| -> VecPerParamSpace<ty::Region>)
 220               -> RegionSubsts {
 221         match self {
 222             ErasedRegions => ErasedRegions,
 223             NonerasedRegions(r) => NonerasedRegions(op(r, a))
 224         }
 225     }
 226 }
 227
 228 ///////////////////////////////////////////////////////////////////////////
 229 // ParamSpace
 230
 231 #[deriving(PartialOrd, Ord, PartialEq, Eq,
 232            Clone, Hash, Encodable, Decodable, Show)]
 233 pub enum ParamSpace {
 234     TypeSpace, // Type parameters attached to a type definition, trait, or impl
 235     SelfSpace, // Self parameter on a trait
 236     FnSpace,   // Type parameters attached to a method or fn
 237 }
 238
 239 impl ParamSpace {
 240     pub fn all() -> [ParamSpace, ..3] {
 241         [TypeSpace, SelfSpace, FnSpace]
 242     }
 243
 244     pub fn to_uint(self) -> uint {
 245         match self {
 246             TypeSpace => 0,
 247             SelfSpace => 1,
 248             FnSpace => 2,
 249         }
 250     }
 251
 252     pub fn from_uint(u: uint) -> ParamSpace {
 253         match u {
 254             0 => TypeSpace,
 255             1 => SelfSpace,
 256             2 => FnSpace,
 257             _ => fail!("Invalid ParamSpace: {}", u)
 258         }
 259     }
 260 }
 261
 262 /**
 263  * Vector of things sorted by param space. Used to keep
 264  * the set of things declared on the type, self, or method
 265  * distinct.
 266  */
 267 #[deriving(PartialEq, Eq, Clone, Hash, Encodable, Decodable)]
 268 pub struct VecPerParamSpace<T> {
 269     // This was originally represented as a tuple with one Vec<T> for
 270     // each variant of ParamSpace, and that remains the abstraction
 271     // that it provides to its clients.
 272     //
 273     // Here is how the representation corresponds to the abstraction
 274     // i.e. the "abstraction function" AF:
 275     //
 276     // AF(self) = (self.content.slice_to(self.type_limit),
 277     //             self.content.slice(self.type_limit, self.self_limit),
 278     //             self.content.slice_from(self.self_limit))
 279     type_limit: uint,
 280     self_limit: uint,
 281     content: Vec<T>,
 282 }
 283
 284 impl<T:fmt::Show> fmt::Show for VecPerParamSpace<T> {
 285     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 286         try!(write!(fmt, "VecPerParamSpace {{"));
 287         for space in ParamSpace::all().iter() {
 288             try!(write!(fmt, "{}: {}, ", *space, self.get_slice(*space)));
 289         }
 290         try!(write!(fmt, "}}"));
 291         Ok(())
 292     }
 293 }
 294
 295 impl<T:Clone> VecPerParamSpace<T> {
 296     pub fn push_all(&mut self, space: ParamSpace, values: &[T]) {
 297         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 298         for t in values.iter() {
 299             self.push(space, t.clone());
 300         }
 301     }
 302 }
 303
 304 impl<T> VecPerParamSpace<T> {
 305     fn limits(&self, space: ParamSpace) -> (uint, uint) {
 306         match space {
 307             TypeSpace => (0, self.type_limit),
 308             SelfSpace => (self.type_limit, self.self_limit),
 309             FnSpace => (self.self_limit, self.content.len()),
 310         }
 311     }
 312
 313     pub fn empty() -> VecPerParamSpace<T> {
 314         VecPerParamSpace {
 315             type_limit: 0,
 316             self_limit: 0,
 317             content: Vec::new()
 318         }
 319     }
 320
 321     pub fn params_from_type(types: Vec<T>) -> VecPerParamSpace<T> {
 322         VecPerParamSpace::empty().with_vec(TypeSpace, types)
 323     }
 324
 325     /// `t` is the type space.
 326     /// `s` is the self space.
 327     /// `f` is the fn space.
 328     pub fn new(t: Vec<T>, s: Vec<T>, f: Vec<T>) -> VecPerParamSpace<T> {
 329         let type_limit = t.len();
 330         let self_limit = t.len() + s.len();
 331         let mut content = t;
 332         content.push_all_move(s);
 333         content.push_all_move(f);
 334         VecPerParamSpace {
 335             type_limit: type_limit,
 336             self_limit: self_limit,
 337             content: content,
 338         }
 339     }
 340
 341     fn new_internal(content: Vec<T>, type_limit: uint, self_limit: uint)
 342                     -> VecPerParamSpace<T>
 343     {
 344         VecPerParamSpace {
 345             type_limit: type_limit,
 346             self_limit: self_limit,
 347             content: content,
 348         }
 349     }
 350
 351     pub fn sort(t: Vec<T>, space: |&T| -> ParamSpace) -> VecPerParamSpace<T> {
 352         let mut result = VecPerParamSpace::empty();
 353         for t in t.move_iter() {
 354             result.push(space(&t), t);
 355         }
 356         result
 357     }
 358
 359     /// Appends `value` to the vector associated with `space`.
 360     ///
 361     /// Unlike the `push` method in `Vec`, this should not be assumed
 362     /// to be a cheap operation (even when amortized over many calls).
 363     pub fn push(&mut self, space: ParamSpace, value: T) {
 364         let (_, limit) = self.limits(space);
 365         match space {
 366             TypeSpace => { self.type_limit += 1; self.self_limit += 1; }
 367             SelfSpace => { self.self_limit += 1; }
 368             FnSpace   => {}
 369         }
 370         self.content.insert(limit, value);
 371     }
 372
 373     pub fn pop(&mut self, space: ParamSpace) -> Option<T> {
 374         let (start, limit) = self.limits(space);
 375         if start == limit {
 376             None
 377         } else {
 378             match space {
 379                 TypeSpace => { self.type_limit -= 1; self.self_limit -= 1; }
 380                 SelfSpace => { self.self_limit -= 1; }
 381                 FnSpace   => {}
 382             }
 383             self.content.remove(limit - 1)
 384         }
 385     }
 386
 387     pub fn truncate(&mut self, space: ParamSpace, len: uint) {
 388         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 389         while self.len(space) > len {
 390             self.pop(space);
 391         }
 392     }
 393
 394     pub fn replace(&mut self, space: ParamSpace, elems: Vec<T>) {
 395         // FIXME (#15435): slow; O(n^2); could enhance vec to make it O(n).
 396         self.truncate(space, 0);
 397         for t in elems.move_iter() {
 398             self.push(space, t);
 399         }
 400     }
 401
 402     pub fn get_self<'a>(&'a self) -> Option<&'a T> {
 403         let v = self.get_slice(SelfSpace);
 404         assert!(v.len() <= 1);
 405         if v.len() == 0 { None } else { Some(&v[0]) }
 406     }
 407
 408     pub fn len(&self, space: ParamSpace) -> uint {
 409         self.get_slice(space).len()
 410     }
 411
 412     pub fn is_empty_in(&self, space: ParamSpace) -> bool {
 413         self.len(space) == 0
 414     }
 415
 416     pub fn get_slice<'a>(&'a self, space: ParamSpace) -> &'a [T] {
 417         let (start, limit) = self.limits(space);
 418         self.content.slice(start, limit)
 419     }
 420
 421     pub fn get_mut_slice<'a>(&'a mut self, space: ParamSpace) -> &'a mut [T] {
 422         let (start, limit) = self.limits(space);
 423         self.content.mut_slice(start, limit)
 424     }
 425
 426     pub fn opt_get<'a>(&'a self,
 427                        space: ParamSpace,
 428                        index: uint)
 429                        -> Option<&'a T> {
 430         let v = self.get_slice(space);
 431         if index < v.len() { Some(&v[index]) } else { None }
 432     }
 433
 434     pub fn get<'a>(&'a self, space: ParamSpace, index: uint) -> &'a T {
 435         &self.get_slice(space)[index]
 436     }
 437
 438     pub fn get_mut<'a>(&'a mut self,
 439                        space: ParamSpace,
 440                        index: uint) -> &'a mut T {
 441         &mut self.get_mut_slice(space)[index]
 442     }
 443
 444     pub fn iter<'a>(&'a self) -> Items<'a,T> {
 445         self.content.iter()
 446     }
 447
 448     pub fn all_vecs(&self, pred: |&[T]| -> bool) -> bool {
 449         let spaces = [TypeSpace, SelfSpace, FnSpace];
 450         spaces.iter().all(|&space| { pred(self.get_slice(space)) })
 451     }
 452
 453     pub fn all(&self, pred: |&T| -> bool) -> bool {
 454         self.iter().all(pred)
 455     }
 456
 457     pub fn any(&self, pred: |&T| -> bool) -> bool {
 458         self.iter().any(pred)
 459     }
 460
 461     pub fn is_empty(&self) -> bool {
 462         self.all_vecs(|v| v.is_empty())
 463     }
 464
 465     pub fn map<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
 466         let result = self.iter().map(pred).collect();
 467         VecPerParamSpace::new_internal(result,
 468                                        self.type_limit,
 469                                        self.self_limit)
 470     }
 471
 472     pub fn map_move<U>(self, pred: |T| -> U) -> VecPerParamSpace<U> {
 473         let (t, s, f) = self.split();
 474         VecPerParamSpace::new(t.move_iter().map(|p| pred(p)).collect(),
 475                               s.move_iter().map(|p| pred(p)).collect(),
 476                               f.move_iter().map(|p| pred(p)).collect())
 477     }
 478
 479     pub fn map_rev<U>(&self, pred: |&T| -> U) -> VecPerParamSpace<U> {
 480         /*!
 481          * Executes the map but in reverse order. For hacky reasons, we rely
 482          * on this in table.
 483          *
 484          * FIXME(#5527) -- order of eval becomes irrelevant with newer
 485          * trait reform, which features an idempotent algorithm that
 486          * can be run to a fixed point
 487          */
 488
 489         let mut fns: Vec<U> = self.get_slice(FnSpace).iter().rev().map(|p| pred(p)).collect();
 490
 491         // NB: Calling foo.rev().map().rev() causes the calls to map
 492         // to occur in the wrong order. This was somewhat surprising
 493         // to me, though it makes total sense.
 494         fns.reverse();
 495
 496         let mut selfs: Vec<U> = self.get_slice(SelfSpace).iter().rev().map(|p| pred(p)).collect();
 497         selfs.reverse();
 498         let mut tys: Vec<U> = self.get_slice(TypeSpace).iter().rev().map(|p| pred(p)).collect();
 499         tys.reverse();
 500         VecPerParamSpace::new(tys, selfs, fns)
 501     }
 502
 503     pub fn split(self) -> (Vec<T>, Vec<T>, Vec<T>) {
 504         // FIXME (#15418): this does two traversals when in principle
 505         // one would suffice.  i.e. change to use `move_iter`.
 506         let VecPerParamSpace { type_limit, self_limit, content } = self;
 507         let mut i = 0;
 508         let (prefix, fn_vec) = content.partition(|_| {
 509             let on_left = i < self_limit;
 510             i += 1;
 511             on_left
 512         });
 513
 514         let mut i = 0;
 515         let (type_vec, self_vec) = prefix.partition(|_| {
 516             let on_left = i < type_limit;
 517             i += 1;
 518             on_left
 519         });
 520
 521         (type_vec, self_vec, fn_vec)
 522     }
 523
 524     pub fn with_vec(mut self, space: ParamSpace, vec: Vec<T>)
 525                     -> VecPerParamSpace<T>
 526     {
 527         assert!(self.is_empty_in(space));
 528         self.replace(space, vec);
 529         self
 530     }
 531 }
 532
 533 ///////////////////////////////////////////////////////////////////////////
 534 // Public trait `Subst`
 535 //
 536 // Just call `foo.subst(tcx, substs)` to perform a substitution across
 537 // `foo`. Or use `foo.subst_spanned(tcx, substs, Some(span))` when
 538 // there is more information available (for better errors).
 539
 540 pub trait Subst {
 541     fn subst(&self, tcx: &ty::ctxt, substs: &Substs) -> Self {
 542         self.subst_spanned(tcx, substs, None)
 543     }
 544
 545     fn subst_spanned(&self, tcx: &ty::ctxt,
 546                      substs: &Substs,
 547                      span: Option<Span>)
 548                      -> Self;
 549 }
 550
 551 impl<T:TypeFoldable> Subst for T {
 552     fn subst_spanned(&self,
 553                      tcx: &ty::ctxt,
 554                      substs: &Substs,
 555                      span: Option<Span>)
 556                      -> T
 557     {
 558         let mut folder = SubstFolder { tcx: tcx,
 559                                        substs: substs,
 560                                        span: span,
 561                                        root_ty: None,
 562                                        ty_stack_depth: 0 };
 563         (*self).fold_with(&mut folder)
 564     }
 565 }
 566
 567 ///////////////////////////////////////////////////////////////////////////
 568 // The actual substitution engine itself is a type folder.
 569
 570 struct SubstFolder<'a, 'tcx: 'a> {
 571     tcx: &'a ty::ctxt<'tcx>,
 572     substs: &'a Substs,
 573
 574     // The location for which the substitution is performed, if available.
 575     span: Option<Span>,
 576
 577     // The root type that is being substituted, if available.
 578     root_ty: Option<ty::t>,
 579
 580     // Depth of type stack
 581     ty_stack_depth: uint,
 582 }
 583
 584 impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
 585     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.tcx }
 586
 587     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 588         // Note: This routine only handles regions that are bound on
 589         // type declarations and other outer declarations, not those
 590         // bound in *fn types*. Region substitution of the bound
 591         // regions that appear in a function signature is done using
 592         // the specialized routine
 593         // `middle::typeck::check::regionmanip::replace_late_regions_in_fn_sig()`.
 594         match r {
 595             ty::ReEarlyBound(_, space, i, region_name) => {
 596                 match self.substs.regions {
 597                     ErasedRegions => ty::ReStatic,
 598                     NonerasedRegions(ref regions) =>
 599                         match regions.opt_get(space, i) {
 600                             Some(t) => *t,
 601                             None => {
 602                                 let span = self.span.unwrap_or(DUMMY_SP);
 603                                 self.tcx().sess.span_bug(
 604                                     span,
 605                                     format!("Type parameter out of range \
 606                                      when substituting in region {} (root type={}) \
 607                                      (space={}, index={})",
 608                                     region_name.as_str(),
 609                                     self.root_ty.repr(self.tcx()),
 610                                     space, i).as_slice());
 611                             }
 612                         }
 613                 }
 614             }
 615             _ => r
 616         }
 617     }
 618
 619     fn fold_ty(&mut self, t: ty::t) -> ty::t {
 620         if !ty::type_needs_subst(t) {
 621             return t;
 622         }
 623
 624         // track the root type we were asked to substitute
 625         let depth = self.ty_stack_depth;
 626         if depth == 0 {
 627             self.root_ty = Some(t);
 628         }
 629         self.ty_stack_depth += 1;
 630
 631         let t1 = match ty::get(t).sty {
 632             ty::ty_param(p) => {
 633                 check(self, p, t, self.substs.types.opt_get(p.space, p.idx))
 634             }
 635             _ => {
 636                 ty_fold::super_fold_ty(self, t)
 637             }
 638         };
 639
 640         assert_eq!(depth + 1, self.ty_stack_depth);
 641         self.ty_stack_depth -= 1;
 642         if depth == 0 {
 643             self.root_ty = None;
 644         }
 645
 646         return t1;
 647
 648         fn check(this: &SubstFolder,
 649                  p: ty::ParamTy,
 650                  source_ty: ty::t,
 651                  opt_ty: Option<&ty::t>)
 652                  -> ty::t {
 653             match opt_ty {
 654                 Some(t) => *t,
 655                 None => {
 656                     let span = this.span.unwrap_or(DUMMY_SP);
 657                     this.tcx().sess.span_bug(
 658                         span,
 659                         format!("Type parameter `{}` ({}) out of range \
 660                                  when substituting (root type={})",
 661                                 p.repr(this.tcx()),
 662                                 source_ty.repr(this.tcx()),
 663                                 this.root_ty.repr(this.tcx())).as_slice());
 664                 }
 665             }
 666         }
 667     }
 668 }