From 4c4e54ac8a9782439744fe15aa31a3bedab92b74 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Thu, 14 Jan 2021 18:47:42 +0300 Subject: prepare to publish el libro de arena --- Cargo.lock | 24 +++-- Cargo.toml | 2 +- crates/arena/Cargo.toml | 10 -- crates/arena/src/lib.rs | 152 --------------------------- crates/arena/src/map.rs | 62 ----------- crates/hir_def/Cargo.toml | 2 +- crates/hir_def/src/adt.rs | 2 +- crates/hir_def/src/attr.rs | 2 +- crates/hir_def/src/body.rs | 2 +- crates/hir_def/src/body/lower.rs | 2 +- crates/hir_def/src/body/scope.rs | 2 +- crates/hir_def/src/db.rs | 2 +- crates/hir_def/src/expr.rs | 2 +- crates/hir_def/src/generics.rs | 2 +- crates/hir_def/src/item_tree.rs | 2 +- crates/hir_def/src/lib.rs | 2 +- crates/hir_def/src/nameres.rs | 2 +- crates/hir_def/src/nameres/collector.rs | 2 +- crates/hir_def/src/src.rs | 2 +- crates/hir_def/src/trace.rs | 2 +- crates/hir_expand/Cargo.toml | 2 +- crates/hir_expand/src/ast_id_map.rs | 2 +- crates/hir_ty/Cargo.toml | 2 +- crates/hir_ty/src/db.rs | 2 +- crates/hir_ty/src/diagnostics/match_check.rs | 2 +- crates/hir_ty/src/infer.rs | 2 +- crates/hir_ty/src/lower.rs | 2 +- crates/profile/Cargo.toml | 3 +- crates/profile/src/tree.rs | 4 +- crates/project_model/Cargo.toml | 2 +- crates/project_model/src/cargo_workspace.rs | 2 +- crates/project_model/src/sysroot.rs | 2 +- lib/README.md | 2 + lib/arena/Cargo.toml | 10 ++ lib/arena/src/lib.rs | 152 +++++++++++++++++++++++++++ lib/arena/src/map.rs | 62 +++++++++++ 36 files changed, 270 insertions(+), 263 deletions(-) delete mode 100644 crates/arena/Cargo.toml delete mode 100644 crates/arena/src/lib.rs delete mode 100644 crates/arena/src/map.rs create mode 100644 lib/README.md create mode 100644 lib/arena/Cargo.toml create mode 100644 lib/arena/src/lib.rs create mode 100644 lib/arena/src/map.rs diff --git a/Cargo.lock b/Cargo.lock index ae99b966e..c715e5e0b 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -36,10 +36,6 @@ version = "0.12.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "33954243bd79057c2de7338850b85983a44588021f8a5fee574a8888c6de4344" -[[package]] -name = "arena" -version = "0.0.0" - [[package]] name = "arrayvec" version = "0.5.2" @@ -547,7 +543,6 @@ name = "hir_def" version = "0.0.0" dependencies = [ "anymap", - "arena", "base_db", "cfg", "drop_bomb", @@ -557,6 +552,7 @@ dependencies = [ "hir_expand", "indexmap", "itertools 0.10.0", + "la-arena 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "log", "mbe", "once_cell", @@ -573,9 +569,9 @@ dependencies = [ name = "hir_expand" version = "0.0.0" dependencies = [ - "arena", "base_db", "either", + "la-arena 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "log", "mbe", "parser", @@ -590,7 +586,6 @@ dependencies = [ name = "hir_ty" version = "0.0.0" dependencies = [ - "arena", "arrayvec", "base_db", "chalk-ir", @@ -601,6 +596,7 @@ dependencies = [ "hir_def", "hir_expand", "itertools 0.10.0", + "la-arena 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "log", "once_cell", "profile", @@ -771,6 +767,16 @@ dependencies = [ "winapi-build", ] +[[package]] +name = "la-arena" +version = "0.1.0" + +[[package]] +name = "la-arena" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0385ab3b926cc05c78275d7ac6799c21fb964ada0a45cdaeaf1415d6a3dda39" + [[package]] name = "lazy_static" version = "1.4.0" @@ -1196,8 +1202,8 @@ version = "0.0.0" name = "profile" version = "0.0.0" dependencies = [ - "arena", "cfg-if 1.0.0", + "la-arena 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "libc", "once_cell", "perf-event", @@ -1208,11 +1214,11 @@ name = "project_model" version = "0.0.0" dependencies = [ "anyhow", - "arena", "base_db", "cargo_metadata", "cfg", "itertools 0.10.0", + "la-arena 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", "log", "paths", "proc_macro_api", diff --git a/Cargo.toml b/Cargo.toml index 59d36fbc1..ff0d9e1ce 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,5 +1,5 @@ [workspace] -members = [ "crates/*", "xtask/" ] +members = [ "xtask/", "lib/*", "crates/*" ] [profile.dev] # Disabling debug info speeds up builds a bunch, diff --git a/crates/arena/Cargo.toml b/crates/arena/Cargo.toml deleted file mode 100644 index 863eedf76..000000000 --- a/crates/arena/Cargo.toml +++ /dev/null @@ -1,10 +0,0 @@ -[package] -name = "arena" -version = "0.0.0" -description = "TBD" -license = "MIT OR Apache-2.0" -authors = ["rust-analyzer developers"] -edition = "2018" - -[lib] -doctest = false diff --git a/crates/arena/src/lib.rs b/crates/arena/src/lib.rs deleted file mode 100644 index 3169aa5b8..000000000 --- a/crates/arena/src/lib.rs +++ /dev/null @@ -1,152 +0,0 @@ -//! Yet another index-based arena. - -use std::{ - fmt, - hash::{Hash, Hasher}, - iter::FromIterator, - marker::PhantomData, - ops::{Index, IndexMut}, -}; - -pub mod map; - -#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct RawId(u32); - -impl From for u32 { - fn from(raw: RawId) -> u32 { - raw.0 - } -} - -impl From for RawId { - fn from(id: u32) -> RawId { - RawId(id) - } -} - -impl fmt::Debug for RawId { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - self.0.fmt(f) - } -} - -impl fmt::Display for RawId { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - self.0.fmt(f) - } -} - -pub struct Idx { - raw: RawId, - _ty: PhantomData T>, -} - -impl Clone for Idx { - fn clone(&self) -> Self { - *self - } -} -impl Copy for Idx {} - -impl PartialEq for Idx { - fn eq(&self, other: &Idx) -> bool { - self.raw == other.raw - } -} -impl Eq for Idx {} - -impl Hash for Idx { - fn hash(&self, state: &mut H) { - self.raw.hash(state) - } -} - -impl fmt::Debug for Idx { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - let mut type_name = std::any::type_name::(); - if let Some(idx) = type_name.rfind(':') { - type_name = &type_name[idx + 1..] - } - write!(f, "Idx::<{}>({})", type_name, self.raw) - } -} - -impl Idx { - pub fn from_raw(raw: RawId) -> Self { - Idx { raw, _ty: PhantomData } - } - pub fn into_raw(self) -> RawId { - self.raw - } -} - -#[derive(Clone, PartialEq, Eq)] -pub struct Arena { - data: Vec, -} - -impl fmt::Debug for Arena { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { - fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish() - } -} - -impl Arena { - pub const fn new() -> Arena { - Arena { data: Vec::new() } - } - pub fn clear(&mut self) { - self.data.clear(); - } - - pub fn len(&self) -> usize { - self.data.len() - } - pub fn is_empty(&self) -> bool { - self.data.is_empty() - } - pub fn alloc(&mut self, value: T) -> Idx { - let id = RawId(self.data.len() as u32); - self.data.push(value); - Idx::from_raw(id) - } - pub fn iter( - &self, - ) -> impl Iterator, &T)> + ExactSizeIterator + DoubleEndedIterator { - self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value)) - } - pub fn shrink_to_fit(&mut self) { - self.data.shrink_to_fit(); - } -} - -impl Default for Arena { - fn default() -> Arena { - Arena { data: Vec::new() } - } -} - -impl Index> for Arena { - type Output = T; - fn index(&self, idx: Idx) -> &T { - let idx = idx.into_raw().0 as usize; - &self.data[idx] - } -} - -impl IndexMut> for Arena { - fn index_mut(&mut self, idx: Idx) -> &mut T { - let idx = idx.into_raw().0 as usize; - &mut self.data[idx] - } -} - -impl FromIterator for Arena { - fn from_iter(iter: I) -> Self - where - I: IntoIterator, - { - Arena { data: Vec::from_iter(iter) } - } -} diff --git a/crates/arena/src/map.rs b/crates/arena/src/map.rs deleted file mode 100644 index 0f33907c0..000000000 --- a/crates/arena/src/map.rs +++ /dev/null @@ -1,62 +0,0 @@ -//! A map from arena IDs to some other type. Space requirement is O(highest ID). - -use std::marker::PhantomData; - -use crate::Idx; - -/// A map from arena IDs to some other type. Space requirement is O(highest ID). -#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct ArenaMap { - v: Vec>, - _ty: PhantomData, -} - -impl ArenaMap, V> { - pub fn insert(&mut self, id: Idx, t: V) { - let idx = Self::to_idx(id); - - self.v.resize_with((idx + 1).max(self.v.len()), || None); - self.v[idx] = Some(t); - } - - pub fn get(&self, id: Idx) -> Option<&V> { - self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) - } - - pub fn get_mut(&mut self, id: Idx) -> Option<&mut V> { - self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) - } - - pub fn values(&self) -> impl Iterator { - self.v.iter().filter_map(|o| o.as_ref()) - } - - pub fn values_mut(&mut self) -> impl Iterator { - self.v.iter_mut().filter_map(|o| o.as_mut()) - } - - pub fn iter(&self) -> impl Iterator, &V)> { - self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) - } - - fn to_idx(id: Idx) -> usize { - u32::from(id.into_raw()) as usize - } - - fn from_idx(idx: usize) -> Idx { - Idx::from_raw((idx as u32).into()) - } -} - -impl std::ops::Index> for ArenaMap, T> { - type Output = T; - fn index(&self, id: Idx) -> &T { - self.v[Self::to_idx(id)].as_ref().unwrap() - } -} - -impl Default for ArenaMap, T> { - fn default() -> Self { - ArenaMap { v: Vec::new(), _ty: PhantomData } - } -} diff --git a/crates/hir_def/Cargo.toml b/crates/hir_def/Cargo.toml index 7ef966cd2..5d21283f7 100644 --- a/crates/hir_def/Cargo.toml +++ b/crates/hir_def/Cargo.toml @@ -20,9 +20,9 @@ fst = { version = "0.4", default-features = false } itertools = "0.10.0" indexmap = "1.4.0" smallvec = "1.4.0" +la-arena = "0.1.0" stdx = { path = "../stdx", version = "0.0.0" } -arena = { path = "../arena", version = "0.0.0" } base_db = { path = "../base_db", version = "0.0.0" } syntax = { path = "../syntax", version = "0.0.0" } profile = { path = "../profile", version = "0.0.0" } diff --git a/crates/hir_def/src/adt.rs b/crates/hir_def/src/adt.rs index 236d6f1b7..237c3d3f9 100644 --- a/crates/hir_def/src/adt.rs +++ b/crates/hir_def/src/adt.rs @@ -2,13 +2,13 @@ use std::sync::Arc; -use arena::{map::ArenaMap, Arena}; use base_db::CrateId; use either::Either; use hir_expand::{ name::{AsName, Name}, InFile, }; +use la_arena::{map::ArenaMap, Arena}; use syntax::ast::{self, NameOwner, VisibilityOwner}; use tt::{Delimiter, DelimiterKind, Leaf, Subtree, TokenTree}; diff --git a/crates/hir_def/src/attr.rs b/crates/hir_def/src/attr.rs index 9e6426b31..5a86823c2 100644 --- a/crates/hir_def/src/attr.rs +++ b/crates/hir_def/src/attr.rs @@ -2,12 +2,12 @@ use std::{ops, sync::Arc}; -use arena::map::ArenaMap; use base_db::CrateId; use cfg::{CfgExpr, CfgOptions}; use either::Either; use hir_expand::{hygiene::Hygiene, name::AsName, AstId, InFile}; use itertools::Itertools; +use la_arena::map::ArenaMap; use mbe::ast_to_token_tree; use syntax::{ ast::{self, AstNode, AttrsOwner}, diff --git a/crates/hir_def/src/body.rs b/crates/hir_def/src/body.rs index d07004b9d..43ee57277 100644 --- a/crates/hir_def/src/body.rs +++ b/crates/hir_def/src/body.rs @@ -8,7 +8,6 @@ pub mod scope; use std::{mem, ops::Index, sync::Arc}; -use arena::{map::ArenaMap, Arena}; use base_db::CrateId; use cfg::CfgOptions; use drop_bomb::DropBomb; @@ -17,6 +16,7 @@ use hir_expand::{ ast_id_map::AstIdMap, diagnostics::DiagnosticSink, hygiene::Hygiene, AstId, ExpandResult, HirFileId, InFile, MacroDefId, }; +use la_arena::{map::ArenaMap, Arena}; use rustc_hash::FxHashMap; use syntax::{ast, AstNode, AstPtr}; use test_utils::mark; diff --git a/crates/hir_def/src/body/lower.rs b/crates/hir_def/src/body/lower.rs index 3dc33f248..27575c537 100644 --- a/crates/hir_def/src/body/lower.rs +++ b/crates/hir_def/src/body/lower.rs @@ -3,13 +3,13 @@ use std::{any::type_name, sync::Arc}; -use arena::Arena; use either::Either; use hir_expand::{ hygiene::Hygiene, name::{name, AsName, Name}, ExpandError, HirFileId, MacroDefId, MacroDefKind, }; +use la_arena::Arena; use rustc_hash::FxHashMap; use syntax::{ ast::{ diff --git a/crates/hir_def/src/body/scope.rs b/crates/hir_def/src/body/scope.rs index 065785da7..49f1427b4 100644 --- a/crates/hir_def/src/body/scope.rs +++ b/crates/hir_def/src/body/scope.rs @@ -1,8 +1,8 @@ //! Name resolution for expressions. use std::sync::Arc; -use arena::{Arena, Idx}; use hir_expand::name::Name; +use la_arena::{Arena, Idx}; use rustc_hash::FxHashMap; use crate::{ diff --git a/crates/hir_def/src/db.rs b/crates/hir_def/src/db.rs index d3bf5b34c..0506a7274 100644 --- a/crates/hir_def/src/db.rs +++ b/crates/hir_def/src/db.rs @@ -1,9 +1,9 @@ //! Defines database & queries for name resolution. use std::sync::Arc; -use arena::map::ArenaMap; use base_db::{salsa, CrateId, SourceDatabase, Upcast}; use hir_expand::{db::AstDatabase, HirFileId}; +use la_arena::map::ArenaMap; use syntax::SmolStr; use crate::{ diff --git a/crates/hir_def/src/expr.rs b/crates/hir_def/src/expr.rs index 76f5721e5..af01d32dc 100644 --- a/crates/hir_def/src/expr.rs +++ b/crates/hir_def/src/expr.rs @@ -12,8 +12,8 @@ //! //! See also a neighboring `body` module. -use arena::{Idx, RawId}; use hir_expand::name::Name; +use la_arena::{Idx, RawId}; use syntax::ast::RangeOp; use crate::{ diff --git a/crates/hir_def/src/generics.rs b/crates/hir_def/src/generics.rs index 9b5b886c2..75eab791a 100644 --- a/crates/hir_def/src/generics.rs +++ b/crates/hir_def/src/generics.rs @@ -4,13 +4,13 @@ //! in rustc. use std::sync::Arc; -use arena::{map::ArenaMap, Arena}; use base_db::FileId; use either::Either; use hir_expand::{ name::{name, AsName, Name}, InFile, }; +use la_arena::{map::ArenaMap, Arena}; use syntax::ast::{self, GenericParamsOwner, NameOwner, TypeBoundsOwner}; use crate::{ diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs index b6f510731..91e42aa0d 100644 --- a/crates/hir_def/src/item_tree.rs +++ b/crates/hir_def/src/item_tree.rs @@ -11,7 +11,6 @@ use std::{ sync::Arc, }; -use arena::{Arena, Idx, RawId}; use ast::{AstNode, NameOwner, StructKind}; use base_db::CrateId; use either::Either; @@ -21,6 +20,7 @@ use hir_expand::{ name::{name, AsName, Name}, HirFileId, InFile, }; +use la_arena::{Arena, Idx, RawId}; use rustc_hash::FxHashMap; use smallvec::SmallVec; use syntax::{ast, match_ast}; diff --git a/crates/hir_def/src/lib.rs b/crates/hir_def/src/lib.rs index 211cb2faf..08ed920c6 100644 --- a/crates/hir_def/src/lib.rs +++ b/crates/hir_def/src/lib.rs @@ -52,12 +52,12 @@ mod test_db; use std::hash::{Hash, Hasher}; -use arena::Idx; use base_db::{impl_intern_key, salsa, CrateId}; use hir_expand::{ ast_id_map::FileAstId, eager::expand_eager_macro, hygiene::Hygiene, AstId, HirFileId, InFile, MacroCallId, MacroCallKind, MacroDefId, MacroDefKind, }; +use la_arena::Idx; use syntax::ast; use crate::builtin_type::BuiltinType; diff --git a/crates/hir_def/src/nameres.rs b/crates/hir_def/src/nameres.rs index 5682e122d..50acc3f54 100644 --- a/crates/hir_def/src/nameres.rs +++ b/crates/hir_def/src/nameres.rs @@ -56,9 +56,9 @@ mod tests; use std::sync::Arc; -use arena::Arena; use base_db::{CrateId, Edition, FileId}; use hir_expand::{diagnostics::DiagnosticSink, name::Name, InFile}; +use la_arena::Arena; use rustc_hash::FxHashMap; use stdx::format_to; use syntax::ast; diff --git a/crates/hir_def/src/nameres/collector.rs b/crates/hir_def/src/nameres/collector.rs index f027fd48d..0cd61698c 100644 --- a/crates/hir_def/src/nameres/collector.rs +++ b/crates/hir_def/src/nameres/collector.rs @@ -1469,8 +1469,8 @@ impl ModCollector<'_, '_> { #[cfg(test)] mod tests { use crate::{db::DefDatabase, test_db::TestDB}; - use arena::Arena; use base_db::{fixture::WithFixture, SourceDatabase}; + use la_arena::Arena; use super::*; diff --git a/crates/hir_def/src/src.rs b/crates/hir_def/src/src.rs index f67244b46..eb29265d9 100644 --- a/crates/hir_def/src/src.rs +++ b/crates/hir_def/src/src.rs @@ -1,7 +1,7 @@ //! Utilities for mapping between hir IDs and the surface syntax. -use arena::map::ArenaMap; use hir_expand::InFile; +use la_arena::map::ArenaMap; use crate::{db::DefDatabase, item_tree::ItemTreeNode, AssocItemLoc, ItemLoc}; diff --git a/crates/hir_def/src/trace.rs b/crates/hir_def/src/trace.rs index fd64e7018..0a9beae8e 100644 --- a/crates/hir_def/src/trace.rs +++ b/crates/hir_def/src/trace.rs @@ -9,7 +9,7 @@ //! absolute offsets. The `Trace` structure (inspired, at least in name, by //! Kotlin's `BindingTrace`) allows use the same code to compute both //! projections. -use arena::{map::ArenaMap, Arena, Idx, RawId}; +use la_arena::{map::ArenaMap, Arena, Idx, RawId}; pub(crate) struct Trace { arena: Option>, diff --git a/crates/hir_expand/Cargo.toml b/crates/hir_expand/Cargo.toml index 9fad2ab94..b535a3d4f 100644 --- a/crates/hir_expand/Cargo.toml +++ b/crates/hir_expand/Cargo.toml @@ -13,8 +13,8 @@ doctest = false log = "0.4.8" either = "1.5.3" rustc-hash = "1.0.0" +la-arena = "0.1.0" -arena = { path = "../arena", version = "0.0.0" } base_db = { path = "../base_db", version = "0.0.0" } syntax = { path = "../syntax", version = "0.0.0" } parser = { path = "../parser", version = "0.0.0" } diff --git a/crates/hir_expand/src/ast_id_map.rs b/crates/hir_expand/src/ast_id_map.rs index f63629b30..f4f6e11fd 100644 --- a/crates/hir_expand/src/ast_id_map.rs +++ b/crates/hir_expand/src/ast_id_map.rs @@ -12,7 +12,7 @@ use std::{ marker::PhantomData, }; -use arena::{Arena, Idx}; +use la_arena::{Arena, Idx}; use syntax::{ast, AstNode, AstPtr, SyntaxNode, SyntaxNodePtr}; /// `AstId` points to an AST node in a specific file. diff --git a/crates/hir_ty/Cargo.toml b/crates/hir_ty/Cargo.toml index b0a453961..436c1405b 100644 --- a/crates/hir_ty/Cargo.toml +++ b/crates/hir_ty/Cargo.toml @@ -20,11 +20,11 @@ scoped-tls = "1" chalk-solve = { version = "0.47", default-features = false } chalk-ir = "0.47" chalk-recursive = "0.47" +la-arena = "0.1.0" stdx = { path = "../stdx", version = "0.0.0" } hir_def = { path = "../hir_def", version = "0.0.0" } hir_expand = { path = "../hir_expand", version = "0.0.0" } -arena = { path = "../arena", version = "0.0.0" } base_db = { path = "../base_db", version = "0.0.0" } profile = { path = "../profile", version = "0.0.0" } syntax = { path = "../syntax", version = "0.0.0" } diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs index f3567c49e..b0e2a3b7d 100644 --- a/crates/hir_ty/src/db.rs +++ b/crates/hir_ty/src/db.rs @@ -2,12 +2,12 @@ use std::sync::Arc; -use arena::map::ArenaMap; use base_db::{impl_intern_key, salsa, CrateId, Upcast}; use hir_def::{ db::DefDatabase, expr::ExprId, ConstParamId, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TypeParamId, VariantId, }; +use la_arena::map::ArenaMap; use crate::{ method_resolution::{InherentImpls, TraitImpls}, diff --git a/crates/hir_ty/src/diagnostics/match_check.rs b/crates/hir_ty/src/diagnostics/match_check.rs index 61c47eec8..fbe760c39 100644 --- a/crates/hir_ty/src/diagnostics/match_check.rs +++ b/crates/hir_ty/src/diagnostics/match_check.rs @@ -218,13 +218,13 @@ //! ``` use std::{iter, sync::Arc}; -use arena::Idx; use hir_def::{ adt::VariantData, body::Body, expr::{Expr, Literal, Pat, PatId}, AdtId, EnumVariantId, StructId, VariantId, }; +use la_arena::Idx; use smallvec::{smallvec, SmallVec}; use crate::{db::HirDatabase, ApplicationTy, InferenceResult, Ty, TypeCtor}; diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs index a14d67c06..46a806b9a 100644 --- a/crates/hir_ty/src/infer.rs +++ b/crates/hir_ty/src/infer.rs @@ -18,7 +18,6 @@ use std::mem; use std::ops::Index; use std::sync::Arc; -use arena::map::ArenaMap; use hir_def::{ body::Body, data::{ConstData, FunctionData, StaticData}, @@ -31,6 +30,7 @@ use hir_def::{ TypeAliasId, VariantId, }; use hir_expand::{diagnostics::DiagnosticSink, name::name}; +use la_arena::map::ArenaMap; use rustc_hash::FxHashMap; use stdx::impl_from; use syntax::SmolStr; diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs index 9594cce8b..68d16f89a 100644 --- a/crates/hir_ty/src/lower.rs +++ b/crates/hir_ty/src/lower.rs @@ -7,7 +7,6 @@ //! This usually involves resolving names, collecting generic arguments etc. use std::{iter, sync::Arc}; -use arena::map::ArenaMap; use base_db::CrateId; use hir_def::{ adt::StructKind, @@ -21,6 +20,7 @@ use hir_def::{ TypeAliasId, TypeParamId, UnionId, VariantId, }; use hir_expand::name::Name; +use la_arena::map::ArenaMap; use smallvec::SmallVec; use stdx::impl_from; use test_utils::mark; diff --git a/crates/profile/Cargo.toml b/crates/profile/Cargo.toml index 4951f1835..096233a09 100644 --- a/crates/profile/Cargo.toml +++ b/crates/profile/Cargo.toml @@ -13,8 +13,7 @@ doctest = false once_cell = "1.3.1" cfg-if = "1" libc = "0.2.73" - -arena = { path = "../arena", version = "0.0.0" } +la-arena = "0.1.0" [target.'cfg(target_os = "linux")'.dependencies] perf-event = "0.4" diff --git a/crates/profile/src/tree.rs b/crates/profile/src/tree.rs index 3fac1f36c..62f0c30b5 100644 --- a/crates/profile/src/tree.rs +++ b/crates/profile/src/tree.rs @@ -1,7 +1,7 @@ //! A simple tree implementation which tries to not allocate all over the place. use std::ops; -use arena::Arena; +use la_arena::Arena; #[derive(Default)] pub(crate) struct Tree { @@ -9,7 +9,7 @@ pub(crate) struct Tree { current_path: Vec<(Idx, Option>)>, } -pub(crate) type Idx = arena::Idx>; +pub(crate) type Idx = la_arena::Idx>; impl Tree { pub(crate) fn start(&mut self) diff --git a/crates/project_model/Cargo.toml b/crates/project_model/Cargo.toml index 855fb83ea..51e7a7070 100644 --- a/crates/project_model/Cargo.toml +++ b/crates/project_model/Cargo.toml @@ -17,8 +17,8 @@ serde = { version = "1.0.106", features = ["derive"] } serde_json = "1.0.48" anyhow = "1.0.26" itertools = "0.10.0" +la-arena = "0.1.0" -arena = { path = "../arena", version = "0.0.0" } cfg = { path = "../cfg", version = "0.0.0" } base_db = { path = "../base_db", version = "0.0.0" } toolchain = { path = "../toolchain", version = "0.0.0" } diff --git a/crates/project_model/src/cargo_workspace.rs b/crates/project_model/src/cargo_workspace.rs index a1ab9c6db..c0ed37fc1 100644 --- a/crates/project_model/src/cargo_workspace.rs +++ b/crates/project_model/src/cargo_workspace.rs @@ -10,10 +10,10 @@ use std::{ }; use anyhow::{Context, Result}; -use arena::{Arena, Idx}; use base_db::Edition; use cargo_metadata::{BuildScript, CargoOpt, Message, MetadataCommand, PackageId}; use itertools::Itertools; +use la_arena::{Arena, Idx}; use paths::{AbsPath, AbsPathBuf}; use rustc_hash::FxHashMap; use stdx::JodChild; diff --git a/crates/project_model/src/sysroot.rs b/crates/project_model/src/sysroot.rs index 95b622715..ff44dae4a 100644 --- a/crates/project_model/src/sysroot.rs +++ b/crates/project_model/src/sysroot.rs @@ -7,7 +7,7 @@ use std::{convert::TryFrom, env, ops, path::PathBuf, process::Command}; use anyhow::{format_err, Result}; -use arena::{Arena, Idx}; +use la_arena::{Arena, Idx}; use paths::{AbsPath, AbsPathBuf}; use crate::utf8_stdout; diff --git a/lib/README.md b/lib/README.md new file mode 100644 index 000000000..6b2eeac2c --- /dev/null +++ b/lib/README.md @@ -0,0 +1,2 @@ +Crates in this directory are published to crates.io and obey semver. +They *could* live in a separate repo, but we want to experiment with a monorepo setup. diff --git a/lib/arena/Cargo.toml b/lib/arena/Cargo.toml new file mode 100644 index 000000000..183a5bb6a --- /dev/null +++ b/lib/arena/Cargo.toml @@ -0,0 +1,10 @@ +[package] +name = "la-arena" +version = "0.1.0" +description = "Thy rope of sands..." +license = "MIT OR Apache-2.0" +authors = ["rust-analyzer developers"] +edition = "2018" + +[lib] +doctest = false diff --git a/lib/arena/src/lib.rs b/lib/arena/src/lib.rs new file mode 100644 index 000000000..3169aa5b8 --- /dev/null +++ b/lib/arena/src/lib.rs @@ -0,0 +1,152 @@ +//! Yet another index-based arena. + +use std::{ + fmt, + hash::{Hash, Hasher}, + iter::FromIterator, + marker::PhantomData, + ops::{Index, IndexMut}, +}; + +pub mod map; + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct RawId(u32); + +impl From for u32 { + fn from(raw: RawId) -> u32 { + raw.0 + } +} + +impl From for RawId { + fn from(id: u32) -> RawId { + RawId(id) + } +} + +impl fmt::Debug for RawId { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +impl fmt::Display for RawId { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.0.fmt(f) + } +} + +pub struct Idx { + raw: RawId, + _ty: PhantomData T>, +} + +impl Clone for Idx { + fn clone(&self) -> Self { + *self + } +} +impl Copy for Idx {} + +impl PartialEq for Idx { + fn eq(&self, other: &Idx) -> bool { + self.raw == other.raw + } +} +impl Eq for Idx {} + +impl Hash for Idx { + fn hash(&self, state: &mut H) { + self.raw.hash(state) + } +} + +impl fmt::Debug for Idx { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let mut type_name = std::any::type_name::(); + if let Some(idx) = type_name.rfind(':') { + type_name = &type_name[idx + 1..] + } + write!(f, "Idx::<{}>({})", type_name, self.raw) + } +} + +impl Idx { + pub fn from_raw(raw: RawId) -> Self { + Idx { raw, _ty: PhantomData } + } + pub fn into_raw(self) -> RawId { + self.raw + } +} + +#[derive(Clone, PartialEq, Eq)] +pub struct Arena { + data: Vec, +} + +impl fmt::Debug for Arena { + fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish() + } +} + +impl Arena { + pub const fn new() -> Arena { + Arena { data: Vec::new() } + } + pub fn clear(&mut self) { + self.data.clear(); + } + + pub fn len(&self) -> usize { + self.data.len() + } + pub fn is_empty(&self) -> bool { + self.data.is_empty() + } + pub fn alloc(&mut self, value: T) -> Idx { + let id = RawId(self.data.len() as u32); + self.data.push(value); + Idx::from_raw(id) + } + pub fn iter( + &self, + ) -> impl Iterator, &T)> + ExactSizeIterator + DoubleEndedIterator { + self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawId(idx as u32)), value)) + } + pub fn shrink_to_fit(&mut self) { + self.data.shrink_to_fit(); + } +} + +impl Default for Arena { + fn default() -> Arena { + Arena { data: Vec::new() } + } +} + +impl Index> for Arena { + type Output = T; + fn index(&self, idx: Idx) -> &T { + let idx = idx.into_raw().0 as usize; + &self.data[idx] + } +} + +impl IndexMut> for Arena { + fn index_mut(&mut self, idx: Idx) -> &mut T { + let idx = idx.into_raw().0 as usize; + &mut self.data[idx] + } +} + +impl FromIterator for Arena { + fn from_iter(iter: I) -> Self + where + I: IntoIterator, + { + Arena { data: Vec::from_iter(iter) } + } +} diff --git a/lib/arena/src/map.rs b/lib/arena/src/map.rs new file mode 100644 index 000000000..0f33907c0 --- /dev/null +++ b/lib/arena/src/map.rs @@ -0,0 +1,62 @@ +//! A map from arena IDs to some other type. Space requirement is O(highest ID). + +use std::marker::PhantomData; + +use crate::Idx; + +/// A map from arena IDs to some other type. Space requirement is O(highest ID). +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ArenaMap { + v: Vec>, + _ty: PhantomData, +} + +impl ArenaMap, V> { + pub fn insert(&mut self, id: Idx, t: V) { + let idx = Self::to_idx(id); + + self.v.resize_with((idx + 1).max(self.v.len()), || None); + self.v[idx] = Some(t); + } + + pub fn get(&self, id: Idx) -> Option<&V> { + self.v.get(Self::to_idx(id)).and_then(|it| it.as_ref()) + } + + pub fn get_mut(&mut self, id: Idx) -> Option<&mut V> { + self.v.get_mut(Self::to_idx(id)).and_then(|it| it.as_mut()) + } + + pub fn values(&self) -> impl Iterator { + self.v.iter().filter_map(|o| o.as_ref()) + } + + pub fn values_mut(&mut self) -> impl Iterator { + self.v.iter_mut().filter_map(|o| o.as_mut()) + } + + pub fn iter(&self) -> impl Iterator, &V)> { + self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) + } + + fn to_idx(id: Idx) -> usize { + u32::from(id.into_raw()) as usize + } + + fn from_idx(idx: usize) -> Idx { + Idx::from_raw((idx as u32).into()) + } +} + +impl std::ops::Index> for ArenaMap, T> { + type Output = T; + fn index(&self, id: Idx) -> &T { + self.v[Self::to_idx(id)].as_ref().unwrap() + } +} + +impl Default for ArenaMap, T> { + fn default() -> Self { + ArenaMap { v: Vec::new(), _ty: PhantomData } + } +} -- cgit v1.2.3