Project

General

Profile

Actions

Feature #14394

open

Class.descendants

Added by ridiculous (Ryan Buckley) about 6 years ago. Updated about 2 years ago.

Status:
Open
Target version:
-
[ruby-core:85073]

Description

There have been numerous implementations of the method Class.descendants by various gems. However, I can't help but think that this ability should be included in the Ruby language itself. Especially since Ruby already offers the counterpart method Class.ancestors.

Would it possible to add a descendants class method?


Related issues 3 (1 open2 closed)

Related to Ruby master - Feature #9779: Add Module#descendentsOpenActions
Related to Ruby master - Feature #18273: Class#subclassesClosedActions
Related to Ruby master - Bug #18282: Rails CI raises Segmentation fault with ruby 3.1.0dev supporting `Class#descendants`ClosedActions

Updated by shevegen (Robert A. Heiler) about 6 years ago

I do not know if it was suggested before, but it could be discussed
at the ruby developer meeting perhaps (unless it was already rejected).

I think it may be symmetrical to .ancestors too.

To complete your suggestion, could you describe at the least one
use case when this functionality may be useful? The ruby core team
said in the past that they prefer solving real problems - not that
I am saying that you do not have any real problem, mind you; just
so that it can be included here (you mentioned gems that do so but
in the above suggestion there are not yet any specific names; may
also help so that others can have a look as well). But anyway,
these are just my suggestions - feel free to ignore them if you
want to. :)

Updated by ridiculous (Ryan Buckley) about 6 years ago

Thanks for the reply, shevegen, those are helpful questions :)

The gems I've seen implement this are active-support and dry-rb, with other people checking ObjectSpace to get the list (which can be very slow for large apps).

The most common use case for this that I've seen, is implementing the Chain of Responsibility pattern. In this case, we want to find a "handler" class for a certain type of input, from a list of registered classes. Instead of configuring the handlers as a static array, it's easier and more flexible to be able to lookup the list dynamically at runtime. The lookup is done by finding all subclasses of a certain base class. Because there is no fast and out-of-the-box way to do this, I've historically opted for the configured list approach.

Updated by Eregon (Benoit Daloze) about 6 years ago

Could that work with just the Class#inherited hook?
What's the advantage of asking all subclasses/descendents of a class instead?

Updated by Hanmac (Hans Mackowiak) about 6 years ago

"Class#inherited hook" works not for core classes because they are defined before you can define the hook

also should that show only named classes or anonymous somehow too?

@ridiculous (Ryan Buckley): i often see a register method where you register your new class onto a name/key to that handler service

Actions #5

Updated by ridiculous (Ryan Buckley) about 6 years ago

@Hanmac (Hans Mackowiak) yeah, registering with a method or a static list is common practice. But I feel like Ruby can do better.

For many cases, it's possible to track them with the inherited hook, @Erogon. But for something so fundamental, why not include it in the language?

I'm interested in the history, as I see it was presented and even tentatively scheduled for version 2.2 (https://bugs.ruby-lang.org/issues/9779), wondering what happened?

Updated by Eregon (Benoit Daloze) about 6 years ago

I think one part of the discussion was that this features requires classes to explicitly track their subclasses (which is a memory overhead, and it must be a list of weak references to avoid leaking subclasses).
I think MRI now tracks subclasses but didn't use to.
FWIW TruffleRuby currently doesn't need to track subclasses (But doing it would probably not be a very big overhead, we already need to track constants, class vars and methods in each Class so Class objects are anyway not so lightweight).

Updated by fatkodima (Dima Fatko) over 3 years ago

I would like the ruby team to reconsider this feature.

There is a high demand for this and a lot of implementations in the ruby world. Just some of them:

I have implemented something like this multiple times, personally. And would like to have a standard way to get this.

Are you open for a patch?

Updated by shyouhei (Shyouhei Urabe) over 3 years ago

Implementation wise MRI already have rb_class_foreach_subclass(). It can be rather trivial to wrap that C function.

Updated by Hanmac (Hans Mackowiak) over 3 years ago

@fatkodima (Dima Fatko)

how does rb_class_foreach_subclass handle anonymous classes?

if it would add them, how about adding a parameter to this function exclude/include them? (exclude them as default?)

Updated by Eregon (Benoit Daloze) over 3 years ago

Hanmac (Hans Mackowiak) wrote in #note-10:

if it would add them, how about adding a parameter to this function exclude/include them? (exclude them as default?)

I think the user can filter easily based on whatever condition they want, so this method shouldn't bother with that.

This will force all Ruby implementations to keep a weak list of subclasses, which is some memory footprint overhead.
TruffleRuby for instance currently does not track subclasses.

But I'm not against it, and it seems easier to use than tracking with inherited, and so much cleaner than ObjectSpace.each_object.
Seeing the usage in Rails I have often thought we might define such a method in TruffleRuby, because iterating the heap just for this is very inefficient.
So +1 from me.

Updated by marcandre (Marc-Andre Lafortune) over 3 years ago

+1 for this feature from me.

@Hanmac (Hans Mackowiak): if you are referring to singleton classes, they should be excluded:

s = +'hello'
def s.force_singleton_class
  42
end
s.singleton_class < String # => true
String.descendants.include?(s.singleton_class) # => should be false

Note that the base class' inherited method is not called when a singleton class is created.

If not, I agree with @Eregon (Benoit Daloze), no extra filter necessary.

Updated by Hanmac (Hans Mackowiak) over 3 years ago

More like:

class A
end

x = Class.new(A)

y = x.new

How does the GC handle such classes?
Will they get GC'd when there isn't any reference to them anymore?

I checked such classes will get GC'd when there isn't any reference, (i used ObjectSpace for counting)
So this function wouldn't list them anymore when they are gone

Updated by matz (Yukihiro Matsumoto) over 3 years ago

  • Status changed from Open to Feedback

Accepted.

Although on some implementation, #descendants can be slow since it may be implemented by scanning whole object heaps (as ActiveSupport currently does).

Matz.

Updated by ko1 (Koichi Sasada) over 3 years ago

let's clear:

  • self should be is contained or not? AS's method doesn't contain.
  • singleton classes should be excluded.
  • order is random (not specified).
  • performance of this method is not important, or important (calls it many times)?

Updated by byroot (Jean Boussier) over 3 years ago

self should be is contained or not?

I don't think it should no. self < self # => self.

singleton classes should be excluded.

Absolutely.

order is random

Agreed.

performance of this method is not important, or important

As long as it has reasonable performance, and that it's not affected by the size of the heap, it will be fine.

It's used in a few semi-hotspot in Rails, hence why there are two versions of it. A slow one that use ObjectSpace.each_objects and one keeping an array of WeakRef populated by inherited.

Actions #17

Updated by Eregon (Benoit Daloze) over 3 years ago

byroot (Jean Boussier) wrote in #note-16:

self should be is contained or not?

I don't think it should no. self < self # => self.

Module#ancestors includes self.
#descendants is kind of the opposite/complement of mod.ancestors (finds all modules for which mod is in the ancestors, excluding singleton classes).
So unsure if it should or not include self.

As long as it has reasonable performance

I expect Object.descendants to be quite slow, so it depends on how many descendants there are (including singleton classes which might be tracked internally).
Also we probably need to avoid recursion for modules as I think it's not a DAG there.

Updated by byroot (Jean Boussier) over 3 years ago

self < self # => self

I made a mistake meant => false.

I expect Object.descendants to be quite slow

There isn't much use case for it though. But yes, that one just can't be fast no matter the implementation.

Also we probably need to avoid recursion for modules as I think it's not a DAG there.

I don't think modules are a concern. At least in the Active Support implementation only Class instances are considered. It's true that if descendants is seen as the mirror of ancestors then it should include modules, but I'm not so sure about that.

Updated by Eregon (Benoit Daloze) over 3 years ago

byroot (Jean Boussier) wrote in #note-18:

I don't think modules are a concern. At least in the Active Support implementation only Class instances are considered. It's true that if descendants is seen as the mirror of ancestors then it should include modules, but I'm not so sure about that.

The current implementation on the PR includes self, which seems a bit more natural to me, but not a strong opinion.

One can do some_module.descendants but I think indeed some_class.descendants should not include modules (the PR doesn't).

With the current PR:

$ ruby -e 'p Object.descendants'     
[Object, DidYouMean::PlainFormatter, DidYouMean::RequirePathChecker, DidYouMean::TreeSpellChecker, DidYouMean::NullChecker, DidYouMean::KeyErrorChecker, DidYouMean::MethodNameChecker, DidYouMean::VariableNameChecker, DidYouMean::ClassNameChecker, DidYouMean::SpellChecker, Gem::PathSupport, MonitorMixin::ConditionVariable, Monitor, Gem::Dependency, Gem::Version, Gem::Requirement, Gem::Platform, Gem::List, Gem::SpecificationPolicy, Gem::StreamUI::ThreadedDownloadReporter, Gem::StreamUI::SilentDownloadReporter, Gem::StreamUI::VerboseProgressReporter, Gem::StreamUI::SimpleProgressReporter, Gem::StreamUI::SilentProgressReporter, Gem::StreamUI, Gem::SilentUI, Gem::ConsoleUI, Gem::StubSpecification::StubLine, Gem::BasicSpecification, Gem::Specification, Gem::StubSpecification, Gem::ErrorReason, Gem::SourceFetchProblem, Gem::PlatformMismatch, RubyVM::AbstractSyntaxTree::Node, TracePoint, Complex::compatible, Rational::compatible, Fiber, Process::Status, Thread::ConditionVariable, Thread::Queue, Thread::SizedQueue, Thread::Mutex, ThreadGroup, RubyVM::InstructionSequence, Thread::Backtrace::Location, Thread::Backtrace, Thread, Process::Waiter, RubyVM, Ractor, Enumerator::Producer, Enumerator::Yielder, Enumerator::Generator, Enumerator, Enumerator::ArithmeticSequence, Enumerator::Chain, Enumerator::Lazy, ObjectSpace::WeakMap, Binding, UnboundMethod, Method, Proc, Random::Base, Random, Time::tm, Time, Dir, File::Stat, ARGF.class, IO, File, Range, MatchData, Regexp, Struct, #<Class:0x00005641f0f7a228>, #<Class:0x00005641f0f5e3e8>, Process::Tms, Hash, Array, Numeric, Complex, Rational, Float, Integer, Exception, SystemStackError, NoMemoryError, SecurityError, ScriptError, LoadError, Gem::LoadError, Gem::ConflictError, Gem::MissingSpecError, Gem::MissingSpecVersionError, NotImplementedError, SyntaxError, StandardError, NameError, NoMethodError, FiberError, ThreadError, Math::DomainError, LocalJumpError, IOError, EOFError, RegexpError, ZeroDivisionError, SystemCallError, Errno::EXFULL, Errno::EXDEV, Errno::EUSERS, Errno::EUNATCH, Errno::EUCLEAN, Errno::ETXTBSY, Errno::ETOOMANYREFS, Errno::ETIMEDOUT, Errno::ETIME, Errno::ESTRPIPE, Errno::ESTALE, Errno::ESRMNT, Errno::ESRCH, Errno::ESPIPE, Errno::ESOCKTNOSUPPORT, Errno::ESHUTDOWN, Errno::EROFS, Errno::ERFKILL, Errno::ERESTART, Errno::EREMOTEIO, Errno::EREMOTE, Errno::EREMCHG, Errno::ERANGE, Errno::EPROTOTYPE, Errno::EPROTONOSUPPORT, Errno::EPROTO, Errno::EPIPE, Errno::EPFNOSUPPORT, Errno::EPERM, Errno::EOWNERDEAD, Errno::EOVERFLOW, Errno::ENXIO, Errno::ENOTUNIQ, Errno::ENOTTY, Errno::ENOTSUP, Errno::ENOTSOCK, Errno::ENOTRECOVERABLE, Errno::ENOTNAM, Errno::ENOTEMPTY, Errno::ENOTDIR, Errno::ENOTCONN, Errno::ENOTBLK, Errno::ENOSYS, Errno::ENOSTR, Errno::ENOSR, Errno::ENOSPC, Errno::ENOPROTOOPT, Errno::ENOPKG, Errno::ENONET, Errno::ENOMSG, Errno::ENOMEM, Errno::ENOMEDIUM, Errno::ENOLINK, Errno::ENOLCK, Errno::ENOKEY, Errno::ENOEXEC, Errno::ENOENT, Errno::ENODEV, Errno::ENODATA, Errno::ENOCSI, Errno::ENOBUFS, Errno::ENOANO, Errno::ENFILE, Errno::ENETUNREACH, Errno::ENETRESET, Errno::ENETDOWN, Errno::ENAVAIL, Errno::ENAMETOOLONG, Errno::EMULTIHOP, Errno::EMSGSIZE, Errno::EMLINK, Errno::EMFILE, Errno::EMEDIUMTYPE, Errno::ELOOP, Errno::ELNRNG, Errno::ELIBSCN, Errno::ELIBMAX, Errno::ELIBEXEC, Errno::ELIBBAD, Errno::ELIBACC, Errno::EL3RST, Errno::EL3HLT, Errno::EL2NSYNC, Errno::EL2HLT, Errno::EKEYREVOKED, Errno::EKEYREJECTED, Errno::EKEYEXPIRED, Errno::EISNAM, Errno::EISDIR, Errno::EISCONN, Errno::EIO, Errno::EINVAL, Errno::EINTR, Errno::EINPROGRESS, IO::EINPROGRESSWaitWritable, IO::EINPROGRESSWaitReadable, Errno::EILSEQ, Errno::EIDRM, Errno::EHWPOISON, Errno::EHOSTUNREACH, Errno::EHOSTDOWN, Errno::EFBIG, Errno::EFAULT, Errno::EEXIST, Errno::EDQUOT, Errno::EDOTDOT, Errno::EDOM, Errno::EDESTADDRREQ, Errno::EDEADLK, Errno::ECONNRESET, Errno::ECONNREFUSED, Errno::ECONNABORTED, Errno::ECOMM, Errno::ECHRNG, Errno::ECHILD, Errno::ECANCELED, Errno::EBUSY, Errno::EBFONT, Errno::EBADSLT, Errno::EBADRQC, Errno::EBADR, Errno::EBADMSG, Errno::EBADFD, Errno::EBADF, Errno::EBADE, Errno::EALREADY, Errno::EAGAIN, IO::EAGAINWaitWritable, IO::EAGAINWaitReadable, Errno::EAFNOSUPPORT, Errno::EADV, Errno::EADDRNOTAVAIL, Errno::EADDRINUSE, Errno::EACCES, Errno::E2BIG, Errno::NOERROR, EncodingError, Encoding::ConverterNotFoundError, Encoding::InvalidByteSequenceError, Encoding::UndefinedConversionError, Encoding::CompatibilityError, RuntimeError, Gem::Exception, Gem::VerificationError, Gem::RubyVersionMismatch, Gem::RemoteSourceException, Gem::RemoteInstallationSkipped, Gem::RemoteInstallationCancelled, Gem::RemoteError, Gem::OperationNotSupportedError, Gem::InvalidSpecificationException, Gem::InstallError, Gem::RuntimeRequirementNotMetError, Gem::ImpossibleDependenciesError, Gem::GemNotFoundException, Gem::SpecificGemNotFoundException, Gem::FormatException, Gem::FilePermissionError, Gem::EndOfYAMLException, Gem::DocumentError, Gem::UninstallError, Gem::GemNotInHomeException, Gem::DependencyRemovalException, Gem::DependencyError, Gem::UnsatisfiableDependencyError, Gem::DependencyResolutionError, Gem::CommandLineError, Ractor::Error, Ractor::MovedError, Ractor::RemoteError, NoMatchingPatternError, FrozenError, RangeError, FloatDomainError, IndexError, KeyError, StopIteration, ClosedQueueError, Ractor::ClosedError, ArgumentError, Gem::Requirement::BadRequirementError, UncaughtThrowError, TypeError, SignalException, Interrupt, fatal, SystemExit, Gem::SystemExitException, Symbol, String, DidYouMean::ClassNameChecker::ClassName, Warning::buffer, Encoding, FalseClass, TrueClass, Data, Encoding::Converter, NameError::message, NilClass, Module, Class]

(and Kernel.descendants is the same but with Kernel extra).

Unsure if fatal, NameError::message, Warning::buffer, etc should be included. Those would normally be inaccessible in Ruby except via ObjectSpace.

Updated by byroot (Jean Boussier) over 3 years ago

(and Kernel.descendants is the same but with Kernel extra).

I'm not sure Module#descendants is really useful, but I don't see any reason not to have it either.

Updated by Eregon (Benoit Daloze) over 3 years ago

byroot (Jean Boussier) wrote in #note-20:

I'm not sure Module#descendants is really useful, but I don't see any reason not to have it either.

I think tracking subclasses (of classes) is quite simpler than also having to track "which modules include a given module".

Is there a use-case for mod.descendants where mod is a module and not a class?

If not I'd suggest to restrict it to Class#descendants for now.

Updated by byroot (Jean Boussier) over 3 years ago

Is there a use-case for mod.descendants where mod is a module and not a class?

Not that I know of. Active Support implementations only list Class, not Module.

If not I'd suggest to restrict it to Class#descendants for now.

Agreed.

Updated by fatkodima (Dima Fatko) over 3 years ago

While I needed Class#descendants many times, I never had a need for Module#descendants. But I can think of its usefulness.
For example, when inheritance is implemented through modules, but not classes, for example -

a quick search guided me to this: https://github.com/mongodb/mongoid/blob/55e4f8367f3878fbf1aafeef6b6e40b39567f917/lib/mongoid/document.rb#L34-L36
In this case, this implementation would benefit from Module#descendants.

Updated by ko1 (Koichi Sasada) about 3 years ago

Sorry I forget.
I'll implement Class#descendants, but not Module because the spec is not clear yet.

Updated by ko1 (Koichi Sasada) about 3 years ago

  • Status changed from Feedback to Assigned
  • Assignee set to ko1 (Koichi Sasada)

Updated by Eregon (Benoit Daloze) over 2 years ago

Would be good to add this for 3.1, as it will avoid some pretty expensive heap walks (ObjectSpace.each_object) just to get a list of subclasses.

Actions #27

Updated by jeremyevans0 (Jeremy Evans) over 2 years ago

Updated by jeremyevans0 (Jeremy Evans) over 2 years ago

I'd like this feature to make 3.1, so I submitted a pull request for it, borrowing somewhat from @fatkodima's pull request: https://github.com/ruby/ruby/pull/4974

As @ko1 (Koichi Sasada) specified, the receiver is not included in the array, nor are singleton classes. The order is unspecified, but based on the implementation, a subclass will appear before descendants of that subclasses.

Actions #29

Updated by jeremyevans (Jeremy Evans) over 2 years ago

  • Status changed from Assigned to Closed

Applied in changeset git|717ab0bb2ee63dfe76076e0c9f91fbac3a0de4fd.


Add Class#descendants

Doesn't include receiver or singleton classes.

Implements [Feature #14394]

Co-authored-by: fatkodima
Co-authored-by: Benoit Daloze

Actions #30

Updated by byroot (Jean Boussier) over 2 years ago

Actions #31

Updated by byroot (Jean Boussier) over 2 years ago

  • Related to Bug #18282: Rails CI raises Segmentation fault with ruby 3.1.0dev supporting `Class#descendants` added

Updated by ko1 (Koichi Sasada) over 2 years ago

Note:

The internal implementation of subclass iteration seems fragile (difficult to maintain) because it needs to manage with weakref. In fact, our CI shows SEGV in a few times in years (difficult to debug because of its rareness. But we can ignore these bug because it is rare :p).
So personally I don't want to introduce this feature if the feature is not important.

(if this feature is important for Ruby langauge, I think it is better to re-implement with other easy data structures)

Updated by matz (Yukihiro Matsumoto) about 2 years ago

Module#descendants has been proposed too in #9779.
In addition, upon the existence of newly introduced Class#subclasses, the need for Class#descendants is decreased.

Considering those facts, let up postpone introducing Class#descendats for 3.1.
I feel we need more discussion. Sorry for the last-minute change.

Matz.

Updated by jeremyevans0 (Jeremy Evans) about 2 years ago

  • Status changed from Closed to Open

matz (Yukihiro Matsumoto) wrote in #note-33:

Considering those facts, let up postpone introducing Class#descendats for 3.1.

Class#descendants removed at 3bd5f27f737c7d365b7d01c43d77a958c224ab16. We can potentially reintroduce after 3.1 after discussion.

Updated by byroot (Jean Boussier) about 2 years ago

That's unfortunate. The very recently released Rails 7.0.0 will need to be updated, some code paths won't expect Class#subclasses being present, but not Class#descendants.

I'll update Rails tomorrow.

Updated by byroot (Jean Boussier) about 2 years ago

Rails fixed in https://github.com/rails/rails/pull/43951, I'll see if we can get a 7.0.1 release before 3.1.0 is out.

Updated by byroot (Jean Boussier) about 2 years ago

Just curious about the motivation of the revert though. I sin mainly because of the potential Module#descendants?

Because unless I'm missing something, the potential future inclusion of Module#descendants would change the behavior of Class#descendants, as I don't think a Module could ever be the descendant of a Class.

Updated by matz (Yukihiro Matsumoto) about 2 years ago

Sorry for the last minute change. The biggest reason is that we still have several options, so I didn't want to restrict the future possibility.
For example, Class#descendants can either:

  • behave as it was first introduced. Module#descentands may or may not be introduced.
  • be undefined for classes (to be reserved for module hierarchy), just like Class#include
  • not be introduced along with Module#descendants.

I am open to discussion but I don't want to jump on the conclusion.

Matz.

Updated by dgutov (Dmitry Gutov) about 2 years ago

Shouldn't the #descendants method be the reverse of #ancestors?

#ancestors traverses up both class hierarchies and module inclusion chains.

That tells me both Module#descendants and Class#descendants will make sense, and should enumerate both classes and modules that are either derived from the current class, or include the current module (...and descendants of such classes/modules as well).

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0