Skip to content

Commit a1276ff

Browse files
mtoddmtodd
committed
Merge pull request #64 from github/recursive-membership
Recursive group member search strategy
2 parents f7448ee + 7654682 commit a1276ff

File tree

7 files changed

+277
-2
lines changed

7 files changed

+277
-2
lines changed

‎lib/github/ldap.rb

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ class Ldap
99
require 'github/ldap/virtual_group'
1010
require 'github/ldap/virtual_attributes'
1111
require 'github/ldap/instrumentation'
12+
require 'github/ldap/members'
1213
require 'github/ldap/membership_validators'
1314

1415
include Instrumentation

‎lib/github/ldap/domain.rb

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -163,8 +163,11 @@ def search(options, &block)
163163
# Get the entry for this domain.
164164
#
165165
# Returns a Net::LDAP::Entry
166-
def bind
167-
search(size: 1, scope: Net::LDAP::SearchScope_BaseObject).first
166+
def bind(options = {})
167+
options[:size] = 1
168+
options[:scope] = Net::LDAP::SearchScope_BaseObject
169+
options[:attributes] ||= []
170+
search(options).first
168171
end
169172
end
170173
end

‎lib/github/ldap/members.rb

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
require 'github/ldap/members/classic'
2+
require 'github/ldap/members/recursive'
3+
4+
module GitHub
5+
class Ldap
6+
# Provides various strategies for member lookup.
7+
#
8+
# For example:
9+
#
10+
# group = domain.groups(%w(Engineering)).first
11+
# strategy = GitHub::Ldap::Members::Recursive.new(ldap)
12+
# strategy.perform(group) #=> [#<Net::LDAP::Entry>]
13+
#
14+
module Members
15+
# Internal: Mapping of strategy name to class.
16+
STRATEGIES = {
17+
:classic => GitHub::Ldap::Members::Classic,
18+
:recursive => GitHub::Ldap::Members::Recursive
19+
}
20+
end
21+
end
22+
end

‎lib/github/ldap/members/classic.rb

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
module GitHub
2+
class Ldap
3+
module Members
4+
# Look up group members using the existing `Group#members` and
5+
# `Group#subgroups` API.
6+
class Classic
7+
# Internal: The GitHub::Ldap object to search domains with.
8+
attr_reader :ldap
9+
10+
# Public: Instantiate new search strategy.
11+
#
12+
# - ldap: GitHub::Ldap object
13+
# - options: Hash of options (unused)
14+
def initialize(ldap, options = {})
15+
@ldap = ldap
16+
@options = options
17+
end
18+
19+
# Public: Performs search for group members, including groups and
20+
# members of subgroups recursively.
21+
#
22+
# Returns Array of Net::LDAP::Entry objects.
23+
def perform(group_entry)
24+
group = ldap.load_group(group_entry)
25+
group.members + group.subgroups
26+
end
27+
end
28+
end
29+
end
30+
end

‎lib/github/ldap/members/recursive.rb

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
module GitHub
2+
class Ldap
3+
module Members
4+
# Look up group members recursively.
5+
#
6+
# This results in a maximum of `depth` iterations/recursions to look up
7+
# members of a group and its subgroups.
8+
class Recursive
9+
include Filter
10+
11+
DEFAULT_MAX_DEPTH = 9
12+
ATTRS = %w(dn member uniqueMember memberUid)
13+
14+
# Internal: The GitHub::Ldap object to search domains with.
15+
attr_reader :ldap
16+
17+
# Internal: The maximum depth to search for members.
18+
attr_reader :depth
19+
20+
# Public: Instantiate new search strategy.
21+
#
22+
# - ldap: GitHub::Ldap object
23+
# - options: Hash of options
24+
def initialize(ldap, options = {})
25+
@ldap = ldap
26+
@options = options
27+
@depth = options[:depth] || DEFAULT_MAX_DEPTH
28+
end
29+
30+
# Public: Performs search for group members, including groups and
31+
# members of subgroups recursively.
32+
#
33+
# Returns Array of Net::LDAP::Entry objects.
34+
def perform(group)
35+
found = Hash.new
36+
37+
# find members (N queries)
38+
entries = member_entries(group)
39+
return [] if entries.empty?
40+
41+
# track found entries
42+
entries.each do |entry|
43+
found[entry.dn] = entry
44+
end
45+
46+
# descend to `depth` levels, at most
47+
depth.times do |n|
48+
# find every (new, unique) member entry
49+
depth_subentries = entries.each_with_object([]) do |entry, depth_entries|
50+
submembers = entry["member"]
51+
52+
# skip any members we've already found
53+
submembers.reject! { |dn| found.key?(dn) }
54+
55+
# find members of subgroup, including subgroups (N queries)
56+
subentries = member_entries(entry)
57+
next if subentries.empty?
58+
59+
# track found subentries
60+
subentries.each { |entry| found[entry.dn] = entry }
61+
62+
# collect all entries for this depth
63+
depth_entries.concat subentries
64+
end
65+
66+
# stop if there are no more subgroups to search
67+
break if depth_subentries.empty?
68+
69+
# go one level deeper
70+
entries = depth_subentries
71+
end
72+
73+
# return all found entries
74+
found.values
75+
end
76+
77+
# Internal: Fetch member entries, including subgroups, for the given
78+
# entry.
79+
#
80+
# Returns an Array of Net::LDAP::Entry objects.
81+
def member_entries(entry)
82+
entries = []
83+
dns = member_dns(entry)
84+
uids = member_uids(entry)
85+
86+
entries.concat entries_by_uid(uids) unless uids.empty?
87+
entries.concat entries_by_dn(dns) unless dns.empty?
88+
89+
entries
90+
end
91+
private :member_entries
92+
93+
# Internal: Bind a list of DNs to their respective entries.
94+
#
95+
# Returns an Array of Net::LDAP::Entry objects.
96+
def entries_by_dn(members)
97+
members.map do |dn|
98+
ldap.domain(dn).bind(attributes: ATTRS)
99+
end.compact
100+
end
101+
private :entries_by_dn
102+
103+
# Internal: Fetch entries by UID.
104+
#
105+
# Returns an Array of Net::LDAP::Entry objects.
106+
def entries_by_uid(members)
107+
filter = members.map { |uid| Net::LDAP::Filter.eq(ldap.uid, uid) }.reduce(:|)
108+
domains.each_with_object([]) do |domain, entries|
109+
entries.concat domain.search(filter: filter, attributes: ATTRS)
110+
end.compact
111+
end
112+
private :entries_by_uid
113+
114+
# Internal: Returns an Array of String DNs for `groupOfNames` and
115+
# `uniqueGroupOfNames` members.
116+
def member_dns(entry)
117+
MEMBERSHIP_NAMES.each_with_object([]) do |attr_name, members|
118+
members.concat entry[attr_name]
119+
end
120+
end
121+
private :member_dns
122+
123+
# Internal: Returns an Array of String UIDs for PosixGroups members.
124+
def member_uids(entry)
125+
entry["memberUid"]
126+
end
127+
private :member_uids
128+
129+
# Internal: Domains to search through.
130+
#
131+
# Returns an Array of GitHub::Ldap::Domain objects.
132+
def domains
133+
@domains ||= ldap.search_domains.map { |base| ldap.domain(base) }
134+
end
135+
private :domains
136+
end
137+
end
138+
end
139+
end

‎test/members/classic_test.rb

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
require_relative '../test_helper'
2+
3+
class GitHubLdapRecursiveMembersTest < GitHub::Ldap::Test
4+
def setup
5+
@ldap = GitHub::Ldap.new(options.merge(search_domains: %w(dc=github,dc=com)))
6+
@domain = @ldap.domain("dc=github,dc=com")
7+
@entry = @domain.user?('user1')
8+
@strategy = GitHub::Ldap::Members::Classic.new(@ldap)
9+
end
10+
11+
def find_group(cn)
12+
@domain.groups([cn]).first
13+
end
14+
15+
def test_finds_group_members
16+
members = @strategy.perform(find_group("nested-group1")).map(&:dn)
17+
assert_includes members, @entry.dn
18+
end
19+
20+
def test_finds_nested_group_members
21+
members = @strategy.perform(find_group("n-depth-nested-group1")).map(&:dn)
22+
assert_includes members, @entry.dn
23+
end
24+
25+
def test_finds_deeply_nested_group_members
26+
members = @strategy.perform(find_group("n-depth-nested-group9")).map(&:dn)
27+
assert_includes members, @entry.dn
28+
end
29+
30+
def test_finds_posix_group_members
31+
members = @strategy.perform(find_group("posix-group1")).map(&:dn)
32+
assert_includes members, @entry.dn
33+
end
34+
35+
def test_does_not_respect_configured_depth_limit
36+
strategy = GitHub::Ldap::Members::Classic.new(@ldap, depth: 2)
37+
members = strategy.perform(find_group("n-depth-nested-group9")).map(&:dn)
38+
assert_includes members, @entry.dn
39+
end
40+
end

‎test/members/recursive_test.rb

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
require_relative '../test_helper'
2+
3+
class GitHubLdapRecursiveMembersTest < GitHub::Ldap::Test
4+
def setup
5+
@ldap = GitHub::Ldap.new(options.merge(search_domains: %w(dc=github,dc=com)))
6+
@domain = @ldap.domain("dc=github,dc=com")
7+
@entry = @domain.user?('user1')
8+
@strategy = GitHub::Ldap::Members::Recursive.new(@ldap)
9+
end
10+
11+
def find_group(cn)
12+
@domain.groups([cn]).first
13+
end
14+
15+
def test_finds_group_members
16+
members = @strategy.perform(find_group("nested-group1")).map(&:dn)
17+
assert_includes members, @entry.dn
18+
end
19+
20+
def test_finds_nested_group_members
21+
members = @strategy.perform(find_group("n-depth-nested-group1")).map(&:dn)
22+
assert_includes members, @entry.dn
23+
end
24+
25+
def test_finds_deeply_nested_group_members
26+
members = @strategy.perform(find_group("n-depth-nested-group9")).map(&:dn)
27+
assert_includes members, @entry.dn
28+
end
29+
30+
def test_finds_posix_group_members
31+
members = @strategy.perform(find_group("posix-group1")).map(&:dn)
32+
assert_includes members, @entry.dn
33+
end
34+
35+
def test_respects_configured_depth_limit
36+
strategy = GitHub::Ldap::Members::Recursive.new(@ldap, depth: 2)
37+
members = strategy.perform(find_group("n-depth-nested-group9")).map(&:dn)
38+
refute_includes members, @entry.dn
39+
end
40+
end

0 commit comments

Comments
 (0)