# parses a query and makes it into an expression which can be evaluated # # the search engine evals an expression against an array of hashes (each hash being a track) # and selects those matching. It does so using a select which iterates over x, that is calling # the current hash “x”. # # this parser reads a string containing a query and returns a string containing # the Ruby code which can be passed as argument to the search function, that is, an expression # on “x” reading fields from the hash. # # thus, for instance, # # start_date >= 2015-01-01 # # is parsed to: # # “x >= 2015-01-01” # # the code selecting tracks is # # tracks.select { |x| eval(“x >= 2015-01-01”) } # # the following queries are supported: # # location ~ “” # location == “” # start_location ~ “” # end_location “” # # date ==|>=|<= YYYY-MM-DD # year == 2015 # start_date … # end_date … # # duration ==|>=|<= HH:MM:SS # # max_speed ==|>=|<= NUMBER # min_height ==|>=|<= NUMBER # max_height ==|>=|<= NUMBER # # AND and OR can be used to form complex expressions # #[“location ~ "USA"”, “start_location ~ "Africa"”, “end_location ~ "Africa"”, “date >= 2015-01-01”, “start_date <= 2015-01-01”, “date == 2015-01-01”, “duration > 10:00:00”, “duration <= 01:49:50”, “"USA"”, “duration == 10:00:00” ].each.map { |x| QueryParser.new.parse(x) }
class QueryParser
token
LOCATION_GEN # generic location (start or end) LOCATION # start or end location DATE_GEN # generic date (start or end) DATE_FIELD # the "date" field YEAR_FIELD # year (start or end) FIELD MATCH EQUAL OP DATE NUMBER DURATION STRING AND OR '(' ')'
prechigh
left AND left OR
preclow rule
start exp exp : simple_exp { result = "#{val[0]}" } | exp AND exp { result = "((#{val[0]}) and (#{val[2]}))" } | exp OR exp { result = "((#{val[0]}) or (#{val[2]}))" } | '(' exp ')' { result = "(#{val[1]})" } simple_exp: STRING { result = "x[:start_location].include?(#{val[0]}) or x[:end_location].include?(#{val[0]})" } | LOCATION_GEN MATCH STRING { result = "x[:start_location].include?(#{val[2]}) or x[:end_location].include?(#{val[2]})" } | LOCATION_GEN EQUAL STRING { result = "x[:start_location] == #{val[2]} or x[:end_location] == #{val[2]}" } | LOCATION MATCH STRING { result = "x[:#{val[0]}].include?(#{val[2]})" } | LOCATION EQUAL STRING { result = "x[:#{val[0]}] == #{val[2]}" } | DATE_GEN op_or_equal date { result = "x[:start_date] #{val[1]} #{val[2]} or x[:end_date] #{val[1]} #{val[2]}"} | DATE_FIELD op_or_equal date { result = "#{val[0]} #{val[1]} #{val[2]}" } | YEAR_FIELD op_or_equal NUMBER { result = "x[:start_date].year #{val[1]} #{val[2]} or x[:end_date].year #{val[1]} #{val[2]}" } | FIELD op_or_equal value { result = "x[:#{val[0]}] #{val[1]} #{val[2]}" } date : DATE { result = "DateTime.parse(\"#{val[0]}\")" } op_or_equal : OP | EQUAL value: NUMBER | DURATION
end —- header require 'date' —- inner attr_accessor :result
def parse(str)
@tokens = make_tokens str do_parse
end
def next_token
@tokens.shift
end
LOCATION_GEN = /location/ LOCATION = /(start|end)_location/ DATE_GEN = /date/ DATE_FIELD = /(start|end)_date/ YEAR = /year/ FIELD = /(duration|distance(_aerial)?|(min|max)_height|(min|max)_speed|points|bearing)/
def make_tokens str
require 'strscan' result = [] scanner = StringScanner.new str until scanner.empty? case when match = scanner.scan(/(or|OR)/) result << [:OR, nil] when match = scanner.scan(/(and|AND)/) result << [:AND, nil] when match = scanner.scan(/\(/) result << ['(', nil] when match = scanner.scan(/\)/) result << [')', nil] when match = scanner.scan(/[0-9]+-[0-9]+-[0-9]+/) result << [:DATE, match] when match = scanner.scan(/([0-9]+):([0-9]+):([0-9]+)/) seconds = match[6..7].to_i + match[3..4].to_i * 60 + match[0..1].to_i * 3600 result << [:DURATION, seconds] when match = scanner.scan(/[0-9]+(\.[0-9]+)?/) result << [:NUMBER, match] when match = scanner.scan(LOCATION_GEN) result << [:LOCATION_GEN, nil] when match = scanner.scan(LOCATION) result << [:LOCATION, match] when match = scanner.scan(DATE_GEN) result << [:DATE_GEN, nil] when match = scanner.scan(DATE_FIELD) result << [:DATE_FIELD, match] when match = scanner.scan(YEAR) result << [:YEAR_FIELD, nil] when match = scanner.scan(FIELD) result << [:FIELD, match] when match = scanner.scan(/"[^"]+"/) result << [:STRING, match ] when match = scanner.scan(/~/) result << [:MATCH, '~'] when match = scanner.scan(/==/) result << [:EQUAL, '=='] when match = scanner.scan(/>=/) result << [:OP, '>='] when match = scanner.scan(/>/) result << [:OP, '>'] when match = scanner.scan(/<=/) result << [:OP, '<='] when match = scanner.scan(/</) result << [:OP, '<'] when scanner.scan(/\s+/) # ignore whitespace else raise "The lexer can't recognize <#{scanner.peek(5)}>" end end result << [false, false] return result
end