Change internal role storage in Guild to a dict instead of a list.

This adds the following APIs:

* Guild.get_role

This removes the following APIs:

* Guild.role_hierarchy

To compensate for the removed APIs, Guild.roles is now a sorted list
based on hierarchy. The first element will always be the @everyone
role.

This speeds up access at the cost of some memory, theoretically.

9 files changed, 61 insertions, 46 deletions

diff --git a/discord/abc.py b/discord/abc.py
index 0ca11452..8482104a 100644
--- a/discord/abc.py
+++ b/discord/abc.py
@@ -288,8 +288,9 @@ class GuildChannel:
         """Returns a :class:`list` of :class:`Roles` that have been overridden from
         their default values in the :attr:`Guild.roles` attribute."""
         ret = []
+        g = self.guild
         for overwrite in filter(lambda o: o.type == 'role', self._overwrites):
-            role = utils.get(self.guild.roles, id=overwrite.id)
+            role = g.get_role(overwrite.id)
             if role is None:
                 continue
 
@@ -358,8 +359,7 @@ class GuildChannel:
             overwrite = PermissionOverwrite.from_pair(allow, deny)
 
             if ow.type == 'role':
-                # accidentally quadratic
-                target = utils.find(lambda r: r.id == ow.id, self.guild.roles)
+                target = self.guild.get_role(ow.id)
             elif ow.type == 'member':
                 target = self.guild.get_member(ow.id)
 
diff --git a/discord/audit_logs.py b/discord/audit_logs.py
index 06e7b1a3..4e5f8c21 100644
--- a/discord/audit_logs.py
+++ b/discord/audit_logs.py
@@ -71,7 +71,7 @@ def _transform_overwrites(entry, data):
         ow_type = elem['type']
         ow_id = int(elem['id'])
         if ow_type == 'role':
-            target = utils.find(lambda r: r.id == ow_id, entry.guild.roles)
+            target = entry.guild.get_role(ow_id)
         else:
             target = entry._get_member(ow_id)
 
@@ -163,11 +163,11 @@ class AuditLogChanges:
         setattr(first, 'roles', [])
 
         data = []
-        roles = entry.guild.roles
+        g = entry.guild
 
         for e in elem:
             role_id = int(e['id'])
-            role = utils.find(lambda r: r.id == role_id, roles)
+            role = g.get_role(role_id)
 
             if role is None:
                 role = Object(id=role_id)
@@ -235,7 +235,7 @@ class AuditLogEntry:
                 if the_type == 'member':
                     self.extra = self._get_member(instance_id)
                 else:
-                    role = utils.find(lambda r: r.id == instance_id, self.guild.roles)
+                    role = self.guild.get_role(instance_id)
                     if role is None:
                         role = Object(id=instance_id)
                         role.name = self.extra.get('role_name')
@@ -306,7 +306,7 @@ class AuditLogEntry:
         return self._get_member(target_id)
 
     def _convert_target_role(self, target_id):
-        role = utils.find(lambda r: r.id == target_id, self.guild.roles)
+        role = self.guild.get_role(target_id)
         if role is None:
             return Object(id=target_id)
         return role
diff --git a/discord/ext/commands/converter.py b/discord/ext/commands/converter.py
index 461abee7..c9e91211 100644
--- a/discord/ext/commands/converter.py
+++ b/discord/ext/commands/converter.py
@@ -320,8 +320,11 @@ class RoleConverter(IDConverter):
             raise NoPrivateMessage()
 
         match = self._get_id_match(argument) or re.match(r'<@&([0-9]+)>$', argument)
-        params = dict(id=int(match.group(1))) if match else dict(name=argument)
-        result = discord.utils.get(guild.roles, **params)
+        if match:
+            result = guild.get_role(int(match.group(1)))
+        else:
+            result = discord.utils.get(guild._roles.values(), name=argument)
+
         if result is None:
             raise BadArgument('Role "{}" not found.'.format(argument))
         return result
@@ -454,8 +457,8 @@ class clean_content(Converter):
         )
 
         if ctx.guild:
-            def resolve_role(id, *, _find=discord.utils.find, _roles=ctx.guild.roles):
-                r = _find(lambda x: x.id == id, _roles)
+            def resolve_role(_id, *, _find=ctx.guild.get_role):
+                r = _find(_id, _roles)
                 return '@' + r.name if r else '@deleted-role'
 
             transformations.update(
diff --git a/discord/guild.py b/discord/guild.py
index 03274f87..f1c5405e 100644
--- a/discord/guild.py
+++ b/discord/guild.py
@@ -75,8 +75,6 @@ class Guild(Hashable):
     ----------
     name: :class:`str`
         The guild name.
-    roles
-        A :class:`list` of :class:`Role` that the guild has available.
     emojis
         A :class:`tuple` of :class:`Emoji` that the guild owns.
     region: :class:`VoiceRegion`
@@ -121,7 +119,7 @@ class Guild(Hashable):
 
     __slots__ = ('afk_timeout', 'afk_channel', '_members', '_channels', 'icon',
                  'name', 'id', 'unavailable', 'name', 'region', '_state',
-                 '_default_role', 'roles', '_member_count', '_large',
+                 '_default_role', '_roles', '_member_count', '_large',
                  'owner_id', 'mfa_level', 'emojis', 'features',
                  'verification_level', 'explicit_content_filter', 'splash',
                  '_voice_states', '_system_channel_id', )
@@ -181,21 +179,23 @@ class Guild(Hashable):
         # its position because it's stuck at position 0. Luckily x += False
         # is equivalent to adding 0. So we cast the position to a bool and
         # increment it.
-        for r in self.roles:
-            r.position += bool(r.position)
+        for r in self._roles.values():
+            r.position += (not r.is_default())
 
-        self.roles.append(role)
+        self._roles[role.id] = role
 
-    def _remove_role(self, role):
-        # this raises ValueError if it fails..
-        self.roles.remove(role)
+    def _remove_role(self, role_id):
+        # this raises KeyError if it fails..
+        role = self._roles.pop(role_id)
 
         # since it didn't, we can change the positions now
         # basically the same as above except we only decrement
         # the position if we're above the role we deleted.
-        for r in self.roles:
+        for r in self._roles.values():
             r.position -= r.position > role.position
 
+        return role
+
     def _from_data(self, guild):
         # according to Stan, this is always available even if the guild is unavailable
         # I don't have this guarantee when someone updates the guild.
@@ -211,15 +211,20 @@ class Guild(Hashable):
         self.icon = guild.get('icon')
         self.unavailable = guild.get('unavailable', False)
         self.id = int(guild['id'])
-        self.roles = [Role(guild=self, data=r, state=self._state) for r in guild.get('roles', [])]
+        self._roles = {}
+        state = self._state # speed up attribute access
+        for r in guild.get('roles', []):
+            role = Role(guild=self, data=r, state=state)
+            self._roles[role.id] = role
+
         self.mfa_level = guild.get('mfa_level')
-        self.emojis = tuple(map(lambda d: self._state.store_emoji(self, d), guild.get('emojis', [])))
+        self.emojis = tuple(map(lambda d: state.store_emoji(self, d), guild.get('emojis', [])))
         self.features = guild.get('features', [])
         self.splash = guild.get('splash')
         self._system_channel_id = utils._get_as_snowflake(guild, 'system_channel_id')
 
         for mdata in guild.get('members', []):
-            member = Member(data=mdata, guild=self, state=self._state)
+            member = Member(data=mdata, guild=self, state=state)
             self._add_member(member)
 
         self._sync(guild)
@@ -370,10 +375,23 @@ class Guild(Hashable):
         """Returns a :class:`Member` with the given ID. If not found, returns None."""
         return self._members.get(user_id)
 
+    @property
+    def roles(self):
+        """Returns a :class:`list` of the guild's roles in hierarchy order.
+
+        The first element of this list will be the lowest role in the
+        hierarchy.
+        """
+        return sorted(self._roles.values())
+
+    def get_role(self, role_id):
+        """Returns a :class:`Role` with the given ID. If not found, returns None."""
+        return self._roles.get(role_id)
+
     @utils.cached_slot_property('_default_role')
     def default_role(self):
         """Gets the @everyone role that all members have by default."""
-        return utils.find(lambda r: r.is_default(), self.roles)
+        return utils.find(lambda r: r.is_default(), self._roles.values())
 
     @property
     def owner(self):
@@ -458,15 +476,6 @@ class Guild(Hashable):
         """Returns the guild's creation time in UTC."""
         return utils.snowflake_time(self.id)
 
-    @property
-    def role_hierarchy(self):
-        """Returns the guild's roles in the order of the hierarchy.
-
-        The first element of this list will be the highest role in the
-        hierarchy.
-        """
-        return sorted(self.roles, reverse=True)
-
     def get_member_named(self, name):
         """Returns the first member found that matches the name provided.
 
diff --git a/discord/member.py b/discord/member.py
index bf461d88..e407546a 100644
--- a/discord/member.py
+++ b/discord/member.py
@@ -189,8 +189,8 @@ class Member(discord.abc.Messageable, _BaseUser):
     def _update_roles(self, data):
         # update the roles
         self.roles = [self.guild.default_role]
-        for roleid in map(int, data['roles']):
-            role = utils.find(lambda r: r.id == roleid, self.guild.roles)
+        for role_id in map(int, data['roles']):
+            role = self.guild.get_role(role_id)
             if role is not None:
                 self.roles.append(role)
 
diff --git a/discord/message.py b/discord/message.py
index e55b47b4..00c5ef73 100644
--- a/discord/message.py
+++ b/discord/message.py
@@ -309,7 +309,7 @@ class Message:
         self.role_mentions = []
         if self.guild is not None:
             for role_id in map(int, role_mentions):
-                role = utils.get(self.guild.roles, id=role_id)
+                role = self.guild.get_role(role_id)
                 if role is not None:
                     self.role_mentions.append(role)
 
diff --git a/discord/role.py b/discord/role.py
index 086d5e55..4610c7d0 100644
--- a/discord/role.py
+++ b/discord/role.py
@@ -188,10 +188,7 @@ class Role(Hashable):
         http = self._state.http
 
         change_range = range(min(self.position, position), max(self.position, position) + 1)
-        sorted_roles = sorted((x for x in self.guild.roles if x.position in change_range and x.id != self.id),
-                              key=lambda x: x.position)
-
-        roles = [r.id for r in sorted_roles]
+        roles = [r.id for r in self.guild.roles[1:] if x.position in change_range]
 
         if self.position > position:
             roles.insert(0, self.id)
diff --git a/discord/state.py b/discord/state.py
index ea6b89de..7180509a 100644
--- a/discord/state.py
+++ b/discord/state.py
@@ -743,10 +743,9 @@ class ConnectionState:
         guild = self._get_guild(int(data['guild_id']))
         if guild is not None:
             role_id = int(data['role_id'])
-            role = utils.find(lambda r: r.id == role_id, guild.roles)
             try:
-                guild._remove_role(role)
-            except ValueError:
+                role = guild._remove_role(role_id)
+            except KeyError:
                 return
             else:
                 self.dispatch('guild_role_delete', role)
@@ -758,7 +757,7 @@ class ConnectionState:
         if guild is not None:
             role_data = data['role']
             role_id = int(role_data['id'])
-            role = utils.find(lambda r: r.id == role_id, guild.roles)
+            role = guild.get_role(role_id)
             if role is not None:
                 old_role = copy.copy(role)
                 role._update(role_data)
diff --git a/docs/migrating.rst b/docs/migrating.rst
index 074cc2d6..3e9def24 100644
--- a/docs/migrating.rst
+++ b/docs/migrating.rst
@@ -368,11 +368,17 @@ They will be enumerated here.
 
     - Use :attr:`Member.activity` instead.
 
+- ``Guild.role_hierarchy`` / ``Server.role_hierarchy``
+
+    - Use :attr:`Guild.roles` instead. Note that while sorted, it is in the opposite order
+      of what the old ``Guild.role_hierarchy`` used to be.
+
 **Changed**
 
 - :attr:`Member.avatar_url` and :attr:`User.avatar_url` now return the default avatar if a custom one is not set.
 - :attr:`Message.embeds` is now a list of :class:`Embed` instead of ``dict`` objects.
 - :attr:`Message.attachments` is now a list of :class:`Attachment` instead of ``dict`` object.
+- :attr:`Guild.roles` is now sorted through hierarchy. The first element is always the ``@everyone`` role.
 
 **Added**
 
@@ -398,6 +404,7 @@ They will be enumerated here.
 - :attr:`Message.activity` and :attr:`Message.application` for Rich Presence related information.
 - :meth:`TextChannel.is_nsfw` to check if a text channel is NSFW.
 - :meth:`Colour.from_rgb` to construct a :class:`Colour` from RGB tuple.
+- :meth:`Guild.get_role` to get a role by its ID.
 
 .. _migrating_1_0_sending_messages: