class Sexp #:nodoc: ## # Verifies that +pattern+ is a Matcher and then dispatches to its # #=~ method. # # See Matcher.=~ def =~ pattern raise ArgumentError, "Not a pattern: %p" % [pattern] unless Matcher === pattern pattern =~ self end ## # Verifies that +pattern+ is a Matcher and then dispatches to its # #satisfy? method. # # TODO: rename match? def satisfy? pattern raise ArgumentError, "Not a pattern: %p" % [pattern] unless Matcher === pattern pattern.satisfy? self end ## # Verifies that +pattern+ is a Matcher and then dispatches to its #/ # method. # # TODO: rename grep? match_all ? find_all ? def / pattern raise ArgumentError, "Not a pattern: %p" % [pattern] unless Matcher === pattern pattern / self end ## # Recursively searches for the +pattern+ yielding the matches. def search_each pattern, &block # TODO: rename to grep? raise ArgumentError, "Needs a pattern" unless pattern.kind_of? Matcher return enum_for(:search_each, pattern) unless block_given? if pattern.satisfy? self then yield self end self.each_sexp do |subset| subset.search_each pattern, &block end end ## # Recursively searches for the +pattern+ yielding each match, and # replacing it with the result of the block. # def replace_sexp pattern, &block # TODO: rename to gsub? raise ArgumentError, "Needs a pattern" unless pattern.kind_of? Matcher return yield self if pattern.satisfy? self # TODO: Needs #new_from(*new_body) to copy file/line/comment self.class.new(*self.map { |subset| case subset when Sexp then subset.replace_sexp pattern, &block else subset end }) end ## # Matches an S-Expression. # # See Matcher for examples. def self.q *args Matcher.new(*args) end def self.s *args where = caller.first.split(/:/, 3).first(2).join ":" warn "DEPRECATED: use Sexp.q(...) instead. From %s" % [where] q(*args) end ## # Matches any single item. # # See Wild for examples. def self._ Wild.new end # TODO: reorder factory methods and classes to match ## # Matches all remaining input. # # See Remaining for examples. def self.___ Remaining.new end ## # Matches an expression or any expression that includes the child. # # See Include for examples. def self.include child # TODO: rename, name is generic ruby Include.new(child) end ## # Matches any atom. # # See Atom for examples. def self.atom Atom.new end ## # Matches when any of the sub-expressions match. # # This is also available via Matcher#|. # # See Any for examples. def self.any *args Any.new(*args) end ## # Matches only when all sub-expressions match. # # This is also available via Matcher#&. # # See All for examples. def self.all *args All.new(*args) end ## # Matches when sub-expression does not match. # # This is also available via Matcher#-@. # # See Not for examples. def self.not? arg Not.new arg end class << self alias - not? end # TODO: add Sibling factory method? ## # Matches anything that has a child matching the sub-expression. # # See Child for examples. def self.child child Child.new child end ## # Matches anything having the same sexp_type, which is the first # value in a Sexp. # # See Type for examples. def self.t name Type.new name end ## # Matches any atom who's string representation matches the patterns # passed in. # # See Pattern for examples. def self.m *values res = values.map { |value| case value when Regexp then value else re = Regexp.escape value.to_s Regexp.new "\\A%s\\Z" % re end } Pattern.new Regexp.union(*res) end ## # Matches an atom of the specified +klass+ (or module). # # See Pattern for examples. def self.k klass Klass.new klass end ## # Defines a family of objects that can be used to match sexps to # certain types of patterns, much like regexps can be used on # strings. Generally you won't use this class directly. # # You would normally create a matcher using the top-level #s method, # but with a block, calling into the Sexp factory methods. For example: # # s{ s(:class, m(/^Test/), _, ___) } # # This creates a matcher for classes whose names start with "Test". # It uses Sexp.m to create a Sexp::Matcher::Pattern matcher, Sexp._ # to create a Sexp::Matcher::Wild matcher, and Sexp.___ to create a # Sexp::Matcher::Remaining matcher. It works like this: # # s{ # start to create a pattern # s( # create a sexp matcher # :class. # for class nodes # m(/^Test/), # matching name slots that start with "Test" # _, # any superclass value # ___ # and whatever is in the class # ) # } # # Then you can use that with #=~, #/, Sexp#replace_sexp, and others. # # For more examples, see the various Sexp class methods, the examples, # and the tests supplied with Sexp. # # * For pattern creation, see factory methods: Sexp::_, Sexp::___, etc. # * For matching returning truthy/falsey results, see Sexp#=~. # * For case expressions, see Matcher#===. # * For getting all subtree matches, see Sexp#/. # # If rdoc didn't suck, these would all be links. class Matcher < Sexp ## # Should #=~ match sub-trees? def self.match_subs? @@match_subs end ## # Setter for +match_subs?+. def self.match_subs= o @@match_subs = o end self.match_subs = true ## # Does this matcher actually match +o+? Returns falsey if +o+ is # not a Sexp or if any sub-tree of +o+ is not satisfied by or # equal to its corresponding sub-matcher. # #-- # TODO: push this up to Sexp and make this the workhorse # TODO: do the same with ===/satisfy? def satisfy? o return unless o.kind_of?(Sexp) && (length == o.length || Matcher === last && last.greedy?) each_with_index.all? { |child, i| sexp = o.at i if Sexp === child then # TODO: when will this NOT be a matcher? sexp = o.sexp_body i if child.respond_to?(:greedy?) && child.greedy? child.satisfy? sexp else child == sexp end } end ## # Tree equivalent to String#=~, returns true if +self+ matches # +sexp+ as a whole or in a sub-tree (if +match_subs?+). # # TODO: maybe this should NOT be aliased to === ? # # TODO: example def =~ sexp raise ArgumentError, "Can't both be matchers: %p" % [sexp] if Matcher === sexp self.satisfy?(sexp) || (self.class.match_subs? && sexp.each_sexp.any? { |sub| self =~ sub }) end alias === =~ # TODO?: alias === satisfy? ## # Searches through +sexp+ for all sub-trees that match this # matcher and returns a MatchCollection for each match. # # TODO: redirect? # Example: # Q{ s(:b) } / s(:a, s(:b)) => [s(:b)] def / sexp raise ArgumentError, "can't both be matchers" if Matcher === sexp # TODO: move search_each into matcher? MatchCollection.new sexp.search_each(self).to_a end ## # Combines the Matcher with another Matcher, the resulting one will # be satisfied if either Matcher would be satisfied. # # TODO: redirect # Example: # s(:a) | s(:b) def | other Any.new self, other end ## # Combines the Matcher with another Matcher, the resulting one will # be satisfied only if both Matchers would be satisfied. # # TODO: redirect # Example: # t(:a) & include(:b) def & other All.new self, other end ## # Returns a Matcher that matches whenever this Matcher would not have matched # # Example: # -s(:a) def -@ Not.new self end ## # Returns a Matcher that matches if this has a sibling +o+ # # Example: # s(:a) >> s(:b) def >> other Sibling.new self, other end ## # Is this matcher greedy? Defaults to false. def greedy? false end def inspect # :nodoc: s = super s[0] = "q" s end def pretty_print q # :nodoc: q.group 1, "q(", ")" do q.seplist self do |v| q.pp v end end end ## # Parse a lispy string representation of a matcher into a Matcher. # See +Parser+. def self.parse s Parser.new(s).parse end ## # Converts from a lispy string to Sexp matchers in a safe manner. # # "(a 42 _ (c) [t x] ___)" => s{ s(:a, 42, _, s(:c), t(:x), ___) } class Parser ## # The stream of tokens to parse. See #lex. attr_accessor :tokens ## # Create a new Parser instance on +s+ def initialize s self.tokens = lex s end ## # Converts +s+ into a stream of tokens and adds them to +tokens+. def lex s s.scan %r%[()\[\]]|\"[^"]*\"|/[^/]*/|:?[\w?!=~-]+% end ## # Returns the next token and removes it from the stream or raises if empty. def next_token raise SyntaxError, "unbalanced input" if tokens.empty? tokens.shift end ## # Returns the next token without removing it from the stream. def peek_token tokens.first end ## # Parses tokens and returns a +Matcher+ instance. def parse result = parse_sexp until tokens.empty? result end ## # Parses a string into a sexp matcher: # # SEXP : "(" SEXP:args* ")" => Sexp.q(*args) # | "[" CMD:cmd sexp:args* "]" => Sexp.cmd(*args) # | "nil" => nil # | /\d+/:n => n.to_i # | "___" => Sexp.___ # | "_" => Sexp._ # | /^\/(.*)\/$/:re => Regexp.new re[0] # | /^"(.*)"$/:s => String.new s[0] # | UP_NAME:name => Object.const_get name # | NAME:name => name.to_sym # UP_NAME: /[A-Z]\w*/ # NAME : /:?[\w?!=~-]+/ # CMD : "t" | "k" | "m" | "atom" | "not?" | "-" | "any" def parse_sexp token = next_token case token when "(" then parse_list when "[" then parse_cmd when "nil" then nil when /^\d+$/ then token.to_i when "___" then Sexp.___ when "_" then Sexp._ when %r%^/(.*)/$% then re = $1 raise SyntaxError, "Not allowed: /%p/" % [re] unless re =~ /\A([\w()|.*+^$]+)\z/ Regexp.new re when /^"(.*)"$/ then $1 when /^([A-Z]\w*)$/ then Object.const_get $1 when /^:?([\w?!=~-]+)$/ then $1.to_sym else raise SyntaxError, "unhandled token: %p" % [token] end end ## # Parses a balanced list of expressions and returns the # equivalent matcher. def parse_list result = [] result << parse_sexp while peek_token && peek_token != ")" next_token # pop off ")" Sexp.q(*result) end ## # A collection of allowed commands to convert into matchers. ALLOWED = [:t, :m, :k, :atom, :not?, :-, :any].freeze ## # Parses a balanced command. A command is denoted by square # brackets and must conform to a whitelisted set of allowed # commands (see +ALLOWED+). def parse_cmd args = [] args << parse_sexp while peek_token && peek_token != "]" next_token # pop off "]" cmd = args.shift args = Sexp.q(*args) raise SyntaxError, "bad cmd: %p" % [cmd] unless ALLOWED.include? cmd result = Sexp.send cmd, *args result end end # class Parser end # class Matcher ## # Matches any single item. # # examples: # # s(:a) / s{ _ } #=> [s(:a)] # s(:a, s(s(:b))) / s{ s(_) } #=> [s(s(:b))] class Wild < Matcher ## # Matches any single element. def satisfy? o true end def inspect # :nodoc: "_" end def pretty_print q # :nodoc: q.text "_" end end ## # Matches all remaining input. If remaining comes before any other # matchers, they will be ignored. # # examples: # # s(:a) / s{ s(:a, ___ ) } #=> [s(:a)] # s(:a, :b, :c) / s{ s(:a, ___ ) } #=> [s(:a, :b, :c)] class Remaining < Matcher ## # Always satisfied once this is reached. Think of it as a var arg. def satisfy? o true end def greedy? true end def inspect # :nodoc: "___" end def pretty_print q # :nodoc: q.text "___" end end ## # Matches when any of the sub-expressions match. # # This is also available via Matcher#|. # # examples: # # s(:a) / s{ any(s(:a), s(:b)) } #=> [s(:a)] # s(:a) / s{ s(:a) | s(:b) } #=> [s(:a)] # same thing via | # s(:a) / s{ any(s(:b), s(:c)) } #=> [] class Any < Matcher ## # The collection of sub-matchers to match against. attr_reader :options ## # Create an Any matcher which will match any of the +options+. def initialize *options @options = options end ## # Satisfied when any sub expressions match +o+ def satisfy? o options.any? { |exp| Sexp === exp && exp.satisfy?(o) || exp == o } end def == o # :nodoc: super && self.options == o.options end def inspect # :nodoc: options.map(&:inspect).join(" | ") end def pretty_print q # :nodoc: q.group 1, "any(", ")" do q.seplist options do |v| q.pp v end end end end ## # Matches only when all sub-expressions match. # # This is also available via Matcher#&. # # examples: # # s(:a) / s{ all(s(:a), s(:b)) } #=> [] # s(:a, :b) / s{ t(:a) & include(:b)) } #=> [s(:a, :b)] class All < Matcher ## # The collection of sub-matchers to match against. attr_reader :options ## # Create an All matcher which will match all of the +options+. def initialize *options @options = options end ## # Satisfied when all sub expressions match +o+ def satisfy? o options.all? { |exp| exp.kind_of?(Sexp) ? exp.satisfy?(o) : exp == o } end def == o # :nodoc: super && self.options == o.options end def inspect # :nodoc: options.map(&:inspect).join(" & ") end def pretty_print q # :nodoc: q.group 1, "all(", ")" do q.seplist options do |v| q.pp v end end end end ## # Matches when sub-expression does not match. # # This is also available via Matcher#-@. # # examples: # # s(:a) / s{ not?(s(:b)) } #=> [s(:a)] # s(:a) / s{ -s(:b) } #=> [s(:a)] # s(:a) / s{ s(not? :a) } #=> [] class Not < Matcher ## # The value to negate in the match. attr_reader :value ## # Creates a Matcher which will match any Sexp that does not match the +value+ def initialize value @value = value end def == o # :nodoc: super && self.value == o.value end ## # Satisfied if a +o+ does not match the +value+ def satisfy? o !(value.kind_of?(Sexp) ? value.satisfy?(o) : value == o) end def inspect # :nodoc: "not?(%p)" % [value] end def pretty_print q # :nodoc: q.group 1, "not?(", ")" do q.pp value end end end ## # Matches anything that has a child matching the sub-expression # # example: # # s(s(s(s(s(:a))))) / s{ child(s(:a)) } #=> [s(s(s(s(s(:a))))), # s(s(s(s(:a)))), # s(s(s(:a))), # s(s(:a)), # s(:a)] class Child < Matcher ## # The child to match. attr_reader :child ## # Create a Child matcher which will match anything having a # descendant matching +child+. def initialize child @child = child end ## # Satisfied if matches +child+ or +o+ has a descendant matching # +child+. def satisfy? o if child.satisfy? o true elsif o.kind_of? Sexp o.search_each(child).any? end end def == o # :nodoc: super && self.child == o.child end def inspect # :nodoc: "child(%p)" % [child] end def pretty_print q # :nodoc: q.group 1, "child(", ")" do q.pp child end end end ## # Matches any atom (non-Sexp). # # examples: # # s(:a) / s{ s(atom) } #=> [s(:a)] # s(:a, s(:b)) / s{ s(atom) } #=> [s(:b)] class Atom < Matcher ## # Satisfied when +o+ is an atom. def satisfy? o !(o.kind_of? Sexp) end def inspect #:nodoc: "atom" end def pretty_print q # :nodoc: q.text "atom" end end ## # Matches any atom who's string representation matches the patterns # passed in. # # examples: # # s(:a) / s{ m('a') } #=> [s(:a)] # s(:a) / s{ m(/\w/,/\d/) } #=> [s(:a)] # s(:tests, s(s(:test_a), s(:test_b))) / s{ m(/test_\w/) } #=> [s(:test_a), # # TODO: maybe don't require non-sexps? This does respond to =~ now. class Pattern < Matcher ## # The regexp to match for the pattern. attr_reader :pattern def == o # :nodoc: super && self.pattern == o.pattern end ## # Create a Patten matcher which will match any atom that either # matches the input +pattern+. def initialize pattern @pattern = pattern end ## # Satisfied if +o+ is an atom, and +o+ matches +pattern+ def satisfy? o !o.kind_of?(Sexp) && o.to_s =~ pattern # TODO: question to_s end def inspect # :nodoc: "m(%p)" % pattern end def pretty_print q # :nodoc: q.group 1, "m(", ")" do q.pp pattern end end def eql? o super and self.pattern.eql? o.pattern end def hash [super, pattern].hash end end ## # Matches any atom that is an instance of the specified class or module. # # examples: # # s(:lit, 6.28) / s{ q(:lit, k(Float)) } #=> [s(:lit, 6.28)] class Klass < Pattern def satisfy? o o.kind_of? self.pattern end def inspect # :nodoc: "k(%p)" % pattern end def pretty_print q # :nodoc: q.group 1, "k(", ")" do q.pp pattern end end end ## # Matches anything having the same sexp_type, which is the first # value in a Sexp. # # examples: # # s(:a, :b) / s{ t(:a) } #=> [s(:a, :b)] # s(:a, :b) / s{ t(:b) } #=> [] # s(:a, s(:b, :c)) / s{ t(:b) } #=> [s(:b, :c)] class Type < Matcher attr_reader :sexp_type ## # Creates a Matcher which will match any Sexp who's type is +type+, where a type is # the first element in the Sexp. def initialize type @sexp_type = type end def == o # :nodoc: super && self.sexp_type == o.sexp_type end ## # Satisfied if the sexp_type of +o+ is +type+. def satisfy? o o.kind_of?(Sexp) && o.sexp_type == sexp_type end def inspect # :nodoc: "t(%p)" % sexp_type end def pretty_print q # :nodoc: q.group 1, "t(", ")" do q.pp sexp_type end end end ## # Matches an expression or any expression that includes the child. # # examples: # # s(:a, :b) / s{ include(:b) } #=> [s(:a, :b)] # s(s(s(:a))) / s{ include(:a) } #=> [s(:a)] class Include < Matcher ## # The value that should be included in the match. attr_reader :value ## # Creates a Matcher which will match any Sexp that contains the # +value+. def initialize value @value = value end ## # Satisfied if a +o+ is a Sexp and one of +o+'s elements matches # value def satisfy? o Sexp === o && o.any? { |c| # TODO: switch to respond_to?? Sexp === value ? value.satisfy?(c) : value == c } end def == o # :nodoc: super && self.value == o.value end def inspect # :nodoc: "include(%p)" % [value] end def pretty_print q # :nodoc: q.group 1, "include(", ")" do q.pp value end end end ## # See Matcher for sibling relations: <,<<,>>,> class Sibling < Matcher ## # The LHS of the matcher. attr_reader :subject ## # The RHS of the matcher. attr_reader :sibling ## # An optional distance requirement for the matcher. attr_reader :distance ## # Creates a Matcher which will match any pair of Sexps that are siblings. # Defaults to matching the immediate following sibling. def initialize subject, sibling, distance = nil @subject = subject @sibling = sibling @distance = distance end ## # Satisfied if o contains +subject+ followed by +sibling+ def satisfy? o # Future optimizations: # * Shortcut matching sibling subject_matches = index_matches(subject, o) return nil if subject_matches.empty? sibling_matches = index_matches(sibling, o) return nil if sibling_matches.empty? subject_matches.any? { |i1, _data_1| sibling_matches.any? { |i2, _data_2| distance ? (i2-i1 == distance) : i2 > i1 } } end def == o # :nodoc: super && self.subject == o.subject && self.sibling == o.sibling && self.distance == o.distance end def inspect # :nodoc: "%p >> %p" % [subject, sibling] end def pretty_print q # :nodoc: if distance then q.group 1, "sibling(", ")" do q.seplist [subject, sibling, distance] do |v| q.pp v end end else q.group 1 do q.pp subject q.text " >> " q.pp sibling end end end private def index_matches pattern, o indexes = [] return indexes unless o.kind_of? Sexp o.each_with_index do |e, i| data = {} if pattern.kind_of?(Sexp) ? pattern.satisfy?(e) : pattern == o[i] indexes << [i, data] end end indexes end end # class Sibling ## # Wraps the results of a Sexp query. MatchCollection defines # MatchCollection#/ so that you can chain queries. # # For instance: # res = s(:a, s(:b)) / s{ s(:a,_) } / s{ s(:b) } class MatchCollection < Array ## # See Traverse#search def / pattern inject(self.class.new) { |result, match| result.concat match / pattern } end def inspect # :nodoc: "MatchCollection.new(%s)" % self.to_a.inspect[1..-2] end alias :to_s :inspect # :nodoc: def pretty_print q # :nodoc: q.group 1, "MatchCollection.new(", ")" do q.seplist(self) {|v| q.pp v } end end end # class MatchCollection end # class Sexp