From 80d6e5bbd4bb4b2a418e3e81b45b59c01ca00b0c Mon Sep 17 00:00:00 2001
From: "http://jneen.net/" <jneen@jneen.net>
Date: Thu, 6 Apr 2017 14:06:24 -0700
Subject: add a new DeclarativePolicy framework

---
 lib/declarative_policy/base.rb            | 329 ++++++++++++++++++++++++++++++
 lib/declarative_policy/cache.rb           |  32 +++
 lib/declarative_policy/condition.rb       | 102 +++++++++
 lib/declarative_policy/dsl.rb             | 103 ++++++++++
 lib/declarative_policy/preferred_scope.rb |  28 +++
 lib/declarative_policy/rule.rb            | 301 +++++++++++++++++++++++++++
 lib/declarative_policy/runner.rb          | 181 ++++++++++++++++
 lib/declarative_policy/step.rb            |  86 ++++++++
 8 files changed, 1162 insertions(+)
 create mode 100644 lib/declarative_policy/base.rb
 create mode 100644 lib/declarative_policy/cache.rb
 create mode 100644 lib/declarative_policy/condition.rb
 create mode 100644 lib/declarative_policy/dsl.rb
 create mode 100644 lib/declarative_policy/preferred_scope.rb
 create mode 100644 lib/declarative_policy/rule.rb
 create mode 100644 lib/declarative_policy/runner.rb
 create mode 100644 lib/declarative_policy/step.rb

(limited to 'lib/declarative_policy')

diff --git a/lib/declarative_policy/base.rb b/lib/declarative_policy/base.rb
new file mode 100644
index 00000000000..df94cafb6a1
--- /dev/null
+++ b/lib/declarative_policy/base.rb
@@ -0,0 +1,329 @@
+module DeclarativePolicy
+  class Base
+    # A map of ability => list of rules together with :enable
+    # or :prevent actions. Used to look up which rules apply to
+    # a given ability. See Base.ability_map
+    class AbilityMap
+      attr_reader :map
+      def initialize(map = {})
+        @map = map
+      end
+
+      # This merge behavior is different than regular hashes - if both
+      # share a key, the values at that key are concatenated, rather than
+      # overridden.
+      def merge(other)
+        conflict_proc = proc { |key, my_val, other_val| my_val + other_val }
+        AbilityMap.new(@map.merge(other.map, &conflict_proc))
+      end
+
+      def actions(key)
+        @map[key] ||= []
+      end
+
+      def enable(key, rule)
+        actions(key) << [:enable, rule]
+      end
+
+      def prevent(key, rule)
+        actions(key) << [:prevent, rule]
+      end
+    end
+
+    class << self
+      # The `own_ability_map` vs `ability_map` distinction is used so that
+      # the data structure is properly inherited - with subclasses recursively
+      # merging their parent class.
+      #
+      # This pattern is also used for conditions, global_actions, and delegations.
+      def ability_map
+        if self == Base
+          own_ability_map
+        else
+          superclass.ability_map.merge(own_ability_map)
+        end
+      end
+
+      def own_ability_map
+        @own_ability_map ||= AbilityMap.new
+      end
+
+      # an inheritable map of conditions, by name
+      def conditions
+        if self == Base
+          own_conditions
+        else
+          superclass.conditions.merge(own_conditions)
+        end
+      end
+
+      def own_conditions
+        @own_conditions ||= {}
+      end
+
+      # a list of global actions, generated by `prevent_all`. these aren't
+      # stored in `ability_map` because they aren't indexed by a particular
+      # ability.
+      def global_actions
+        if self == Base
+          own_global_actions
+        else
+          superclass.global_actions + own_global_actions
+        end
+      end
+
+      def own_global_actions
+        @own_global_actions ||= []
+      end
+
+      # an inheritable map of delegations, indexed by name (which may be
+      # autogenerated)
+      def delegations
+        if self == Base
+          own_delegations
+        else
+          superclass.delegations.merge(own_delegations)
+        end
+      end
+
+      def own_delegations
+        @own_delegations ||= {}
+      end
+
+      # all the [rule, action] pairs that apply to a particular ability.
+      # we combine the specific ones looked up in ability_map with the global
+      # ones.
+      def configuration_for(ability)
+        ability_map.actions(ability) + global_actions
+      end
+
+      ### declaration methods ###
+
+      def delegate(name = nil, &delegation_block)
+        if name.nil?
+          @delegate_name_counter ||= 0
+          @delegate_name_counter += 1
+          name = :"anonymous_#{@delegate_name_counter}"
+        end
+
+        name = name.to_sym
+
+        if delegation_block.nil?
+          delegation_block = proc { @subject.__send__(name) }
+        end
+
+        own_delegations[name] = delegation_block
+      end
+
+      # Declares a rule, constructed using RuleDsl, and returns
+      # a PolicyDsl which is used for registering the rule with
+      # this class. PolicyDsl will call back into Base.enable_when,
+      # Base.prevent_when, and Base.prevent_all_when.
+      def rule(&b)
+        rule = RuleDsl.new(self).instance_eval(&b)
+        PolicyDsl.new(self, rule)
+      end
+
+      # A hash in which to store calls to `desc` and `with_scope`, etc.
+      def last_options
+        @last_options ||= {}.with_indifferent_access
+      end
+
+      # retrieve and zero out the previously set options (used in .condition)
+      def last_options!
+        last_options.tap { @last_options = nil }
+      end
+
+      # Declare a description for the following condition. Currently unused,
+      # but opens the potential for explaining to users why they were or were
+      # not able to do something.
+      def desc(description)
+        last_options[:description] = description
+      end
+
+      def with_options(opts = {})
+        last_options.merge!(opts)
+      end
+
+      def with_scope(scope)
+        with_options scope: scope
+      end
+
+      def with_score(score)
+        with_options score: score
+      end
+
+      # Declares a condition. It gets stored in `own_conditions`, and generates
+      # a query method based on the condition's name.
+      def condition(name, opts = {}, &value)
+        name = name.to_sym
+
+        opts = last_options!.merge(opts)
+        opts[:context_key] ||= self.name
+
+        condition = Condition.new(name, opts, &value)
+
+        self.own_conditions[name] = condition
+
+        define_method(:"#{name}?") { condition(name).pass? }
+      end
+
+      # These next three methods are mainly called from PolicyDsl,
+      # and are responsible for "inverting" the relationship between
+      # an ability and a rule. We store in `ability_map` a map of
+      # abilities to rules that affect them, together with a
+      # symbol indicating :prevent or :enable.
+      def enable_when(abilities, rule)
+        abilities.each { |a| own_ability_map.enable(a, rule) }
+      end
+
+      def prevent_when(abilities, rule)
+        abilities.each { |a| own_ability_map.prevent(a, rule) }
+      end
+
+      # we store global prevents (from `prevent_all`) separately,
+      # so that they can be combined into every decision made.
+      def prevent_all_when(rule)
+        own_global_actions << [:prevent, rule]
+      end
+    end
+
+    # A policy object contains a specific user and subject on which
+    # to compute abilities. For this reason it's sometimes called
+    # "context" within the framework.
+    #
+    # It also stores a reference to the cache, so it can be used
+    # to cache computations by e.g. ManifestCondition.
+    attr_reader :user, :subject, :cache
+    def initialize(user, subject, opts = {})
+      @user = user
+      @subject = subject
+      @cache = opts[:cache] || {}
+    end
+
+    # helper for checking abilities on this and other subjects
+    # for the current user.
+    def can?(ability, new_subject = :_self)
+      return allowed?(ability) if new_subject == :_self
+
+      policy_for(new_subject).allowed?(ability)
+    end
+
+    # This is the main entry point for permission checks. It constructs
+    # or looks up a Runner for the given ability and asks it if it passes.
+    def allowed?(*abilities)
+      abilities.all? { |a| runner(a).pass? }
+    end
+
+    # The inverse of #allowed?, used mainly in specs.
+    def disallowed?(*abilities)
+      abilities.all? { |a| !runner(a).pass? }
+    end
+
+    # computes the given ability and prints a helpful debugging output
+    # showing which 
+    def debug(ability, *a)
+      runner(ability).debug(*a)
+    end
+
+    desc "Unknown user"
+    condition(:anonymous, scope: :user, score: 0) { @user.nil? }
+
+    desc "By default"
+    condition(:default, scope: :global, score: 0) { true }
+
+    def repr
+      subject_repr =
+        if @subject.respond_to?(:id)
+          "#{@subject.class.name}/#{@subject.id}"
+        else
+          @subject.inspect
+        end
+
+      user_repr =
+        if @user
+          @user.to_reference
+        else
+          "<anonymous>"
+        end
+
+      "(#{user_repr} : #{subject_repr})"
+    end
+
+    def inspect
+      "#<#{self.class.name} #{repr}>"
+    end
+
+    # returns a Runner for the given ability, capable of computing whether
+    # the ability is allowed. Runners are cached on the policy (which itself
+    # is cached on @cache), and caches its result. This is how we perform caching
+    # at the ability level.
+    def runner(ability)
+      ability = ability.to_sym
+      @runners ||= {}
+      @runners[ability] ||=
+        begin
+          delegated_runners = delegated_policies.values.compact.map { |p| p.runner(ability) }
+          own_runner = Runner.new(own_steps(ability))
+          delegated_runners.inject(own_runner, &:merge_runner)
+        end
+    end
+
+    # Helpers for caching. Used by ManifestCondition in performing condition
+    # computation.
+    #
+    # NOTE we can't use ||= here because the value might be the
+    # boolean `false`
+    def cache(key, &b)
+      return @cache[key] if cached?(key)
+      @cache[key] = yield
+    end
+
+    def cached?(key)
+      !@cache[key].nil?
+    end
+
+    # returns a ManifestCondition capable of computing itself. The computation
+    # will use our own @cache.
+    def condition(name)
+      name = name.to_sym
+      @_conditions ||= {}
+      @_conditions[name] ||=
+        begin
+          raise "invalid condition #{name}" unless self.class.conditions.key?(name)
+          ManifestCondition.new(self.class.conditions[name], self)
+        end
+    end
+
+    # used in specs - returns true if there is no possible way for any action
+    # to be allowed, determined only by the global :prevent_all rules.
+    def banned?
+      global_steps = self.class.global_actions.map { |(action, rule)| Step.new(self, rule, action) }
+      !Runner.new(global_steps).pass?
+    end
+
+    # A list of other policies that we've delegated to (see `Base.delegate`)
+    def delegated_policies
+      @delegated_policies ||= self.class.delegations.transform_values do |block|
+        new_subject = instance_eval(&block)
+
+        # never delegate to nil, as that would immediately prevent_all
+        next if new_subject.nil?
+
+        policy_for(new_subject)
+      end
+    end
+
+    def policy_for(other_subject)
+      DeclarativePolicy.policy_for(@user, other_subject, cache: @cache)
+    end
+
+    protected
+
+    # constructs steps that come from this policy and not from any delegations
+    def own_steps(ability)
+      rules = self.class.configuration_for(ability)
+      rules.map { |(action, rule)| Step.new(self, rule, action) }
+    end
+  end
+end
diff --git a/lib/declarative_policy/cache.rb b/lib/declarative_policy/cache.rb
new file mode 100644
index 00000000000..b8cc60074c7
--- /dev/null
+++ b/lib/declarative_policy/cache.rb
@@ -0,0 +1,32 @@
+module DeclarativePolicy
+  module Cache
+    class << self
+      def user_key(user)
+        return '<anonymous>' if user.nil?
+        id_for(user)
+      end
+
+      def policy_key(user, subject)
+        u = user_key(user)
+        s = subject_key(subject)
+        "/dp/policy/#{u}/#{s}"
+      end
+
+      def subject_key(subject)
+        return '<nil>' if subject.nil?
+        return subject.inspect if subject.is_a?(Symbol)
+        "#{subject.class.name}:#{id_for(subject)}"
+      end
+
+      private
+
+      def id_for(obj)
+        if obj.respond_to?(:id) && obj.id
+          obj.id.to_s
+        else
+          "##{obj.object_id}"
+        end
+      end
+    end
+  end
+end
diff --git a/lib/declarative_policy/condition.rb b/lib/declarative_policy/condition.rb
new file mode 100644
index 00000000000..9d7cf6b9726
--- /dev/null
+++ b/lib/declarative_policy/condition.rb
@@ -0,0 +1,102 @@
+module DeclarativePolicy
+  # A Condition is the data structure that is created by the
+  # `condition` declaration on DeclarativePolicy::Base. It is
+  # more or less just a struct of the data passed to that
+  # declaration. It holds on to the block to be instance_eval'd
+  # on a context (instance of Base) later, via #compute.
+  class Condition
+    attr_reader :name, :description, :scope
+    attr_reader :manual_score
+    attr_reader :context_key
+    def initialize(name, opts = {}, &compute)
+      @name = name
+      @compute = compute
+      @scope = opts.fetch(:scope, :normal)
+      @description = opts.delete(:description)
+      @context_key = opts[:context_key]
+      @manual_score = opts.fetch(:score, nil)
+    end
+
+    def compute(context)
+      !!context.instance_eval(&@compute)
+    end
+
+    def key
+      "#{@context_key}/#{@name}"
+    end
+  end
+
+  # In contrast to a Condition, a ManifestCondition contains
+  # a Condition and a context object, and is capable of calculating
+  # a result itself. This is the return value of Base#condition.
+  class ManifestCondition
+    def initialize(condition, context)
+      @condition = condition
+      @context = context
+    end
+
+    # The main entry point - does this condition pass? We reach into
+    # the context's cache here so that we can share in the global
+    # cache (often RequestStore or similar).
+    def pass?
+      @context.cache(cache_key) { @condition.compute(@context) }
+    end
+
+    # Whether we've already computed this condition.
+    def cached?
+      @context.cached?(cache_key)
+    end
+
+    # This is used to score Rule::Condition. See Rule::Condition#score
+    # and Runner#steps_by_score for how scores are used.
+    #
+    # The number here is intended to represent, abstractly, how
+    # expensive it would be to calculate this condition.
+    #
+    # See #cache_key for info about @condition.scope.
+    def score
+      # If we've been cached, no computation is necessary.
+      return 0 if cached?
+
+      # Use the override from condition(score: ...) if present
+      return @condition.manual_score if @condition.manual_score
+
+      # Global scope rules are cheap due to max cache sharing
+      return 2 if  @condition.scope == :global
+
+      # "Normal" rules can't share caches with any other policies
+      return 16 if @condition.scope == :normal
+
+      # otherwise, we're :user or :subject scope, so it's 4 if
+      # the caller has declared a preference
+      return 4 if @condition.scope == DeclarativePolicy.preferred_scope
+
+      # and 8 for all other :user or :subject scope conditions.
+      8
+    end
+
+    private
+
+    # This method controls the caching for the condition. This is where
+    # the condition(scope: ...) option comes into play. Notice that
+    # depending on the scope, we may cache only by the user or only by
+    # the subject, resulting in sharing across different policy objects.
+    def cache_key
+      case @condition.scope
+      when :normal  then "/dp/condition/#{@condition.key}/#{user_key},#{subject_key}"
+      when :user    then "/dp/condition/#{@condition.key}/#{user_key}"
+      when :subject then "/dp/condition/#{@condition.key}/#{subject_key}"
+      when :global  then "/dp/condition/#{@condition.key}"
+      else raise 'invalid scope'
+      end
+    end
+
+    def user_key
+      Cache.user_key(@context.user)
+    end
+
+    def subject_key
+      Cache.subject_key(@context.subject)
+    end
+  end
+end
diff --git a/lib/declarative_policy/dsl.rb b/lib/declarative_policy/dsl.rb
new file mode 100644
index 00000000000..b26807a7622
--- /dev/null
+++ b/lib/declarative_policy/dsl.rb
@@ -0,0 +1,103 @@
+module DeclarativePolicy
+  # The DSL evaluation context inside rule { ... } blocks.
+  # Responsible for creating and combining Rule objects.
+  #
+  # See Base.rule
+  class RuleDsl
+    def initialize(context_class)
+      @context_class = context_class
+    end
+
+    def can?(ability)
+      Rule::Ability.new(ability)
+    end
+
+    def all?(*rules)
+      Rule::And.make(rules)
+    end
+
+    def any?(*rules)
+      Rule::Or.make(rules)
+    end
+
+    def none?(*rules)
+      ~Rule::Or.new(rules)
+    end
+
+    def cond(condition)
+      Rule::Condition.new(condition)
+    end
+
+    def delegate(delegate_name, condition)
+      Rule::DelegatedCondition.new(delegate_name, condition)
+    end
+
+    def method_missing(m, *a, &b)
+      return super unless a.size == 0 && !block_given?
+
+      if @context_class.delegations.key?(m)
+        DelegateDsl.new(self, m)
+      else
+        cond(m.to_sym)
+      end
+    end
+  end
+
+  # Used when the name of a delegate is mentioned in
+  # the rule DSL.
+  class DelegateDsl
+    def initialize(rule_dsl, delegate_name)
+      @rule_dsl = rule_dsl
+      @delegate_name = delegate_name
+    end
+
+    def method_missing(m, *a, &b)
+      return super unless a.size == 0 && !block_given?
+
+      @rule_dsl.delegate(@delegate_name, m)
+    end
+  end
+
+  # The return value of a rule { ... } declaration.
+  # Can call back to register rules with the containing
+  # Policy class (context_class here). See Base.rule
+  #
+  # Note that the #policy method just performs an #instance_eval,
+  # which is useful for multiple #enable or #prevent callse.
+  #
+  # Also provides a #method_missing proxy to the context
+  # class's class methods, so that helper methods can be
+  # defined and used in a #policy { ... } block.
+  class PolicyDsl
+    def initialize(context_class, rule)
+      @context_class = context_class
+      @rule = rule
+    end
+
+    def policy(&b)
+      instance_eval(&b)
+    end
+
+    def enable(*abilities)
+      @context_class.enable_when(abilities, @rule)
+    end
+
+    def prevent(*abilities)
+      @context_class.prevent_when(abilities, @rule)
+    end
+
+    def prevent_all
+      @context_class.prevent_all_when(@rule)
+    end
+
+    def method_missing(m, *a, &b)
+      return super unless @context_class.respond_to?(m)
+
+      @context_class.__send__(m, *a, &b)
+    end
+
+    def respond_to_missing?(m)
+      @context_class.respond_to?(m) || super
+    end
+  end
+end
diff --git a/lib/declarative_policy/preferred_scope.rb b/lib/declarative_policy/preferred_scope.rb
new file mode 100644
index 00000000000..b0754098149
--- /dev/null
+++ b/lib/declarative_policy/preferred_scope.rb
@@ -0,0 +1,28 @@
+module DeclarativePolicy
+  PREFERRED_SCOPE_KEY = :"DeclarativePolicy.preferred_scope"
+
+  class << self
+    def with_preferred_scope(scope, &b)
+      Thread.current[PREFERRED_SCOPE_KEY], old_scope = scope, Thread.current[PREFERRED_SCOPE_KEY]
+      yield
+    ensure
+      Thread.current[PREFERRED_SCOPE_KEY] = old_scope
+    end
+
+    def preferred_scope
+      Thread.current[PREFERRED_SCOPE_KEY]
+    end
+
+    def user_scope(&b)
+      with_preferred_scope(:user, &b)
+    end
+
+    def subject_scope(&b)
+      with_preferred_scope(:subject, &b)
+    end
+
+    def preferred_scope=(scope)
+      Thread.current[PREFERRED_SCOPE_KEY] = scope
+    end
+  end
+end
diff --git a/lib/declarative_policy/rule.rb b/lib/declarative_policy/rule.rb
new file mode 100644
index 00000000000..bfcec241489
--- /dev/null
+++ b/lib/declarative_policy/rule.rb
@@ -0,0 +1,301 @@
+module DeclarativePolicy
+  module Rule
+    # A Rule is the object that results from the `rule` declaration,
+    # usually built using the DSL in `RuleDsl`. It is a basic logical
+    # combination of building blocks, and is capable of deciding,
+    # given a context (instance of DeclarativePolicy::Base) whether it
+    # passes or not. Note that this decision doesn't by itself know
+    # how that affects the actual ability decision - for that, a
+    # `Step` is used.
+    class Base
+      def self.make(*a)
+        new(*a).simplify
+      end
+
+      # true or false whether this rule passes.
+      # `context` is a policy - an instance of
+      # DeclarativePolicy::Base.
+      def pass?(context)
+        raise 'abstract'
+      end
+
+      # same as #pass? except refuses to do any I/O,
+      # returning nil if the result is not yet cached.
+      # used for accurately scoring And/Or
+      def cached_pass?(context)
+        raise 'abstract'
+      end
+
+      # abstractly, how long would it take to compute
+      # this rule? lower-scored rules are tried first.
+      def score(context)
+        raise 'abstract'
+      end
+
+      # unwrap double negatives and nested and/or
+      def simplify
+        self
+      end
+
+      # convenience combination methods
+      def or(other)
+        Or.make([self, other])
+      end
+
+      def and(other)
+        And.make([self, other])
+      end
+
+      def negate
+        Not.make(self)
+      end
+
+      alias_method :|, :or
+      alias_method :&, :and
+      alias_method :~@, :negate
+
+      def inspect
+        "#<Rule #{repr}>"
+      end
+    end
+
+    # A rule that checks a condition. This is the
+    # type of rule that results from a basic bareword
+    # in the rule dsl (see RuleDsl#method_missing).
+    class Condition < Base
+      def initialize(name)
+        @name = name
+      end
+
+      # we delegate scoring to the condition. See
+      # ManifestCondition#score.
+      def score(context)
+        context.condition(@name).score
+      end
+
+      # Let the ManifestCondition from the context
+      # decide whether we pass.
+      def pass?(context)
+        context.condition(@name).pass?
+      end
+
+      # returns nil unless it's already cached
+      def cached_pass?(context)
+        condition = context.condition(@name)
+        return nil unless condition.cached?
+        condition.pass?
+      end
+
+      def description(context)
+        context.class.conditions[@name].description
+      end
+
+      def repr
+        @name.to_s
+      end
+    end
+
+    # A rule constructed from DelegateDsl - using a condition from a
+    # delegated policy.
+    class DelegatedCondition < Base
+      # Internal use only - this is rescued each time it's raised.
+      MissingDelegate = Class.new(StandardError)
+
+      def initialize(delegate_name, name)
+        @delegate_name = delegate_name
+        @name = name
+      end
+
+      def delegated_context(context)
+        policy = context.delegated_policies[@delegate_name]
+        raise MissingDelegate if policy.nil?
+        policy
+      end
+
+      def score(context)
+        delegated_context(context).condition(@name).score
+      rescue MissingDelegate
+        0
+      end
+
+      def cached_pass?(context)
+        condition = delegated_context(context).condition(@name)
+        return nil unless condition.cached?
+        condition.pass?
+      rescue MissingDelegate
+        false
+      end
+
+      def pass?(context)
+        delegated_context(context).condition(@name).pass?
+      rescue MissingDelegate
+        false
+      end
+
+      def repr
+        "#{@delegate_name}.#{@name}"
+      end
+    end
+
+    # A rule constructed from RuleDsl#can?. Computes a different ability
+    # on the same subject.
+    class Ability < Base
+      attr_reader :ability
+      def initialize(ability)
+        @ability = ability
+      end
+
+      # We ask the ability's runner for a score
+      def score(context)
+        context.runner(@ability).score
+      end
+
+      def pass?(context)
+        context.allowed?(@ability)
+      end
+
+      def cached_pass?(context)
+        runner = context.runner(@ability)
+        return nil unless runner.cached?
+        runner.pass?
+      end
+
+      def description(context)
+        "User can #{@ability.inspect}"
+      end
+
+      def repr
+        "can?(#{@ability.inspect})"
+      end
+    end
+
+    # Logical `and`, containing a list of rules. Only passes
+    # if all of them do.
+    class And < Base
+      attr_reader :rules
+      def initialize(rules)
+        @rules = rules
+      end
+
+      def simplify
+        simplified_rules = @rules.flat_map do |rule|
+          simplified = rule.simplify
+          case simplified
+          when And then simplified.rules
+          else [simplified]
+          end
+        end
+
+        And.new(simplified_rules)
+      end
+
+      def score(context)
+        return 0 unless cached_pass?(context).nil?
+
+        # note that cached rules will have score 0 anyways.
+        @rules.map { |r| r.score(context) }.inject(0, :+)
+      end
+
+      def pass?(context)
+        # try to find a cached answer before
+        # checking in order
+        cached = cached_pass?(context)
+        return cached unless cached.nil?
+
+        @rules.all? { |r| r.pass?(context) }
+      end
+
+      def cached_pass?(context)
+        passes = @rules.map { |r| r.cached_pass?(context) }
+        return false if passes.any? { |p| p == false }
+        return true if passes.all? { |p| p == true }
+
+        nil
+      end
+
+      def repr
+        "all?(#{rules.map(&:repr).join(', ')})"
+      end
+    end
+
+    # Logical `or`. Mirrors And.
+    class Or < Base
+      attr_reader :rules
+      def initialize(rules)
+        @rules = rules
+      end
+
+      def pass?(context)
+        cached = cached_pass?(context)
+        return cached unless cached.nil?
+
+        @rules.any? { |r| r.pass?(context) }
+      end
+
+      def simplify
+        simplified_rules = @rules.flat_map do |rule|
+          simplified = rule.simplify
+          case simplified
+          when Or then simplified.rules
+          else [simplified]
+          end
+        end
+
+        Or.new(simplified_rules)
+      end
+
+      def cached_pass?(context)
+        passes = @rules.map { |r| r.cached_pass?(context) }
+        return true if passes.any? { |p| p == true }
+        return false if passes.all? { |p| p == false }
+
+        nil
+      end
+
+      def score(context)
+        return 0 unless cached_pass?(context).nil?
+        @rules.map { |r| r.score(context) }.inject(0, :+)
+      end
+
+      def repr
+        "any?(#{@rules.map(&:repr).join(', ')})"
+      end
+    end
+
+    class Not < Base
+      attr_reader :rule
+      def initialize(rule)
+        @rule = rule
+      end
+
+      def simplify
+        case @rule
+        when And then Or.new(@rule.rules.map(&:negate)).simplify
+        when Or then And.new(@rule.rules.map(&:negate)).simplify
+        when Not then @rule.rule.simplify
+        else Not.new(@rule.simplify)
+        end
+      end
+
+      def pass?(context)
+        !@rule.pass?(context)
+      end
+
+      def cached_pass?(context)
+        case @rule.cached_pass?(context)
+        when nil then nil
+        when true then false
+        when false then true
+        end
+      end
+
+      def score(context)
+        @rule.score(context)
+      end
+
+      def repr
+        "~#{@rule.repr}"
+      end
+    end
+  end
+end
diff --git a/lib/declarative_policy/runner.rb b/lib/declarative_policy/runner.rb
new file mode 100644
index 00000000000..b5c615da4e3
--- /dev/null
+++ b/lib/declarative_policy/runner.rb
@@ -0,0 +1,181 @@
+module DeclarativePolicy
+  class Runner
+    class State
+      def initialize
+        @enabled = false
+        @prevented = false
+      end
+
+      def enable!
+        @enabled = true
+      end
+
+      def enabled?
+        @enabled
+      end
+
+      def prevent!
+        @prevented = true
+      end
+
+      def prevented?
+        @prevented
+      end
+
+      def pass?
+        !prevented? && enabled?
+      end
+    end
+
+    # a Runner contains a list of Steps to be run.
+    attr_reader :steps
+    def initialize(steps)
+      @steps = steps
+    end
+
+    # We make sure only to run any given Runner once,
+    # and just continue to use the resulting @state
+    # that's left behind.
+    def cached?
+      !!@state
+    end
+
+    # used by Rule::Ability. See #steps_by_score
+    def score
+      return 0 if cached?
+      steps.map(&:score).inject(0, :+)
+    end
+
+    def merge_runner(other)
+      Runner.new(@steps + other.steps)
+    end
+
+    # The main entry point, called for making an ability decision.
+    # See #run and DeclarativePolicy::Base#can?
+    def pass?
+      run unless cached?
+
+      @state.pass?
+    end
+
+    # see DeclarativePolicy::Base#debug
+    def debug(out = $stderr)
+      run(out)
+    end
+
+    private
+
+    def flatten_steps!
+      @steps = @steps.flat_map { |s| s.flattened(@steps) }
+    end
+
+    # This method implements the semantic of "one enable and no prevents".
+    # It relies on #steps_by_score for the main loop, and updates @state
+    # with the result of the step.
+    def run(debug = nil)
+      @state = State.new
+
+      steps_by_score do |step, score|
+        passed = nil
+        case step.action
+        when :enable then
+          # we only check :enable actions if they have a chance of
+          # changing the outcome - if no other rule has enabled or
+          # prevented.
+          unless @state.enabled? || @state.prevented?
+            passed = step.pass?
+            @state.enable! if passed
+          end
+
+          debug << inspect_step(step, score, passed) if debug
+        when :prevent then
+          # we only check :prevent actions if the state hasn't already
+          # been prevented.
+          unless @state.prevented?
+            passed = step.pass?
+            if passed
+              @state.prevent!
+              return unless debug
+            end
+          end
+
+          debug << inspect_step(step, score, passed) if debug
+        else raise "invalid action #{step.action.inspect}"
+        end
+      end
+
+      @state
+    end
+
+    # This is the core spot where all those `#score` methods matter.
+    # It is critcal for performance to run steps in the correct order,
+    # so that we don't compute expensive conditions (potentially n times
+    # if we're called on, say, a large list of users).
+    #
+    # In order to determine the cheapest step to run next, we rely on
+    # Step#score, which returns a numerical rating of how expensive
+    # it would be to calculate - the lower the better. It would be
+    # easy enough to statically sort by these scores, but we can do
+    # a little better - the scores are cache-aware (conditions that
+    # are already in the cache have score 0), which means that running
+    # a step can actually change the scores of other steps.
+    #
+    # So! The way we sort here involves re-scoring at every step. This
+    # is by necessity quadratic, but most of the time the number of steps
+    # will be low. But just in case, if the number of steps exceeds 50,
+    # we print a warning and fall back to a static sort.
+    #
+    # For each step, we yield the step object along with the computed score
+    # for debugging purposes.
+    def steps_by_score(&b)
+      flatten_steps!
+
+      if @steps.size > 50
+        warn "DeclarativePolicy: large number of steps (#{steps.size}), falling back to static sort"
+
+        @steps.map { |s| [s.score, s] }.sort_by { |(score, _)| score }.each do |(score, step)|
+          yield step, score
+        end
+
+        return
+      end
+
+      steps = Set.new(@steps)
+
+      loop do
+        return if steps.empty?
+
+        # if the permission hasn't yet been enabled and we only have
+        # prevent steps left, we short-circuit the state here
+        @state.prevent! if !@state.enabled? && steps.all?(&:prevent?)
+
+        lowest_score = Float::INFINITY
+        next_step = nil
+
+        steps.each do |step|
+          score = step.score
+          if score < lowest_score
+            next_step = step
+            lowest_score = score
+          end
+        end
+
+        steps.delete(next_step)
+
+        yield next_step, lowest_score
+      end
+    end
+
+    # Formatter for debugging output.
+    def inspect_step(step, original_score, passed)
+      symbol =
+        case passed
+        when true then '+'
+        when false then '-'
+        when nil then ' '
+        end
+
+      "#{symbol} [#{original_score.to_i}] #{step.repr}\n"
+    end
+  end
+end
diff --git a/lib/declarative_policy/step.rb b/lib/declarative_policy/step.rb
new file mode 100644
index 00000000000..3469fe9f991
--- /dev/null
+++ b/lib/declarative_policy/step.rb
@@ -0,0 +1,86 @@
+module DeclarativePolicy
+  # This object represents one step in the runtime decision of whether
+  # an ability is allowed. It contains a Rule and a context (instance
+  # of DeclarativePolicy::Base), which contains the user, the subject,
+  # and the cache. It also contains an "action", which is the symbol
+  # :prevent or :enable.
+  class Step
+    attr_reader :context, :rule, :action
+    def initialize(context, rule, action)
+      @context = context
+      @rule = rule
+      @action = action
+    end
+
+    # In the flattening process, duplicate steps may be generated in the
+    # same rule. This allows us to eliminate those (see Runner#steps_by_score
+    # and note its use of a Set)
+    def ==(other)
+      @context == other.context && @rule == other.rule && @action == other.action
+    end
+
+    # In the runner, steps are sorted dynamically by score, so that
+    # we are sure to compute them in close to the optimal order.
+    #
+    # See also Rule#score, ManifestCondition#score, and Runner#steps_by_score.
+    def score
+      # we slightly prefer the preventative actions
+      # since they are more likely to short-circuit
+      case @action
+      when :prevent
+        @rule.score(@context) * (7.0 / 8)
+      when :enable
+        @rule.score(@context)
+      end
+    end
+
+    def with_action(action)
+      Step.new(@context, @rule, action)
+    end
+
+    def enable?
+      @action == :enable
+    end
+
+    def prevent?
+      @action == :prevent
+    end
+
+    # This rather complex method allows us to split rules into parts so that
+    # they can be sorted independently for better optimization
+    def flattened(roots)
+      case @rule
+      when Rule::Or
+        # A single `Or` step is the same as each of its elements as separate steps
+        @rule.rules.flat_map { |r| Step.new(@context, r, @action).flattened(roots) }
+      when Rule::Ability
+        # This looks like a weird micro-optimization but it buys us quite a lot
+        # in some cases. If we depend on an Ability (i.e. a `can?(...)` rule),
+        # and that ability *only* has :enable actions (modulo some actions that
+        # we already have taken care of), then its rules can be safely inlined.
+        steps = @context.runner(@rule.ability).steps.reject { |s| roots.include?(s) }
+
+        if steps.all?(&:enable?)
+          # in the case that we are a :prevent step, each inlined step becomes
+          # an independent :prevent, even though it was an :enable in its initial
+          # context.
+          steps.map! { |s| s.with_action(:prevent) } if prevent?
+
+          steps.flat_map { |s| s.flattened(roots) }
+        else
+          [self]
+        end
+      else
+        [self]
+      end
+    end
+
+    def pass?
+      @rule.pass?(@context)
+    end
+
+    def repr
+      "#{@action} when #{@rule.repr} (#{@context.repr})"
+    end
+  end
+end
-- 
cgit v1.2.1