commit 1d2e9540a364fdbb4e2ff79e1caab6833c678c3c
Author: quantumish <freifeld.david@gmail.com>
Date: Tue, 19 Mar 2024 23:38:51 -0400
Initial commit
Diffstat:
6 files changed, 282 insertions(+), 0 deletions(-)
diff --git a/install.sh b/install.sh
@@ -0,0 +1,9 @@
+wget https://smlnj.org/dist/working/110.99.5/config.tgz
+mkdir smlnj
+tar -xf config.tgz -C smlnj
+cd smlnj && config/install.sh && cd ..
+export PATH=$(pwd)/smlnj/bin:$PATH
+ml-build minisql.cm Main.main minisql-image
+
+
+
diff --git a/minisql b/minisql
@@ -0,0 +1,2 @@
+#!/bin/bash
+smlnj/bin/sml @SMLload minisql-image.*
diff --git a/minisql.cm b/minisql.cm
@@ -0,0 +1,6 @@
+Group is
+
+ minisql.sml
+ $/json-lib.cm
+ $/smlnj-lib.cm
+ $/basis.cm
+\ No newline at end of file
diff --git a/minisql.sml b/minisql.sml
@@ -0,0 +1,209 @@
+type columnref = string;
+type tableref = string;
+(* Object containing (key, value) pairs. *)
+type row = JSON.value;
+(* List of values that gets displayed to user. *)
+type rowvals = JSON.value list;
+
+datatype value = String of string | Int of int | Column of columnref
+datatype binop = Eq of (value * value) | Neq of (value * value) | Gt of (value * value) | Lt of (value * value)
+datatype pred = Expr of binop | And of pred * pred | Or of pred * pred
+datatype targets = Columns of columnref list | All
+datatype query = Select of (targets * tableref * pred option * int option)
+
+exception Parse
+exception BadQuery
+exception Type
+exception MalformedData
+
+(*--------------------------- Parsing logic. -----------------------------*)
+
+structure P = ParserComb
+
+fun skipWS parser = P.skipBefore Char.isSpace parser
+
+(* Sequentially combines two parsers. *)
+fun *> (a, b) = P.seq (a, b)
+infixr 3 *>
+(* Combines two parsers, ignoring whitespace. *)
+fun +> (a, b) = P.seq (a, skipWS(b))
+infixr 3 +>
+(* Only keeps the right hand result. *)
+fun %> (a, b) = P.wrap(a +> b, #2)
+infixr 3 %>
+(* Only keeps the left hand result. *)
+fun @> (a, b) = P.wrap(a +> b, #1)
+infixr 3 @>
+
+(* Parses "ref" values: e.g. name of column or table *)
+fun parseRef getc = (P.token (fn x => Char.isAlphaNum x orelse x = #"_")) getc
+
+(* Parses a list of one or more target columns (including wildcard) *)
+fun parseCols getc = P.or(
+ P.wrap(P.string "*", (fn _ => All)),
+ P.wrap(parseRef +> P.zeroOrMore((P.char #",") %> parseRef), (Columns o op::))
+ ) getc
+
+fun middle (_, (x, _)) = x
+fun isQuote x = (x = #"'" orelse x = #"\"")
+fun parseValue getc = P.or'([
+ P.wrap((P.eatChar isQuote) *> P.token (fn x => not (isQuote x))
+ *> (P.eatChar isQuote), (String o middle)),
+ P.wrap(Int.scan StringCvt.DEC, Int),
+ P.wrap(parseRef, Column)
+ ]) getc
+
+fun parseBinop getc = P.or'([
+ P.wrap(parseValue +> P.char #"=" %> parseValue, Eq),
+ P.wrap(parseValue +> P.char #">" %> parseValue, Gt),
+ P.wrap(parseValue +> P.char #"<" %> parseValue, Lt),
+ P.wrap(parseValue +> P.string "!=" %> parseValue, Neq)
+ ]) getc
+
+fun parseSubexpr getc = P.or'([
+ P.wrap(parseBinop, Expr),
+ parseNested
+ ]) getc
+and parseNested getc = (P.char #"(" %> P.or(
+ P.wrap(parseSubexpr +> P.string "AND" %> parseSubexpr, And),
+ P.wrap(parseSubexpr +> P.string "OR" %> parseSubexpr, Or)
+ ) @> P.char #")") getc
+
+fun parsePredicate getc = P.or'([
+ P.wrap(parseSubexpr +> P.string "AND" %> parseSubexpr, And),
+ P.wrap(parseSubexpr +> P.string "OR" %> parseSubexpr, Or),
+ P.wrap(parseBinop, Expr)
+ ]) getc
+
+(* Optionally applies a parser. On failure, parses to NONE instead of passing
+ * an actual failure up and causing the overall parse to fail. *)
+fun parseOptional parser getc = P.or (P.wrap (parser, SOME), P.result NONE) getc
+
+fun parseSelect getc =
+ P.wrap((P.string "SELECT ") %> parseCols +> (P.string "FROM ") %> parseRef
+ *> parseOptional(skipWS(P.string "WHERE ") %> parsePredicate)
+ *> parseOptional(skipWS(P.string "LIMIT ") %> (Int.scan StringCvt.DEC))
+ @> P.char(#";"), (fn (cs, (t, (p, l))) => Select (cs, t, p, l))) getc
+
+fun parse s = Option.valOf (StringCvt.scanString parseSelect s)
+ handle Option => raise Parse
+
+(*--------------------------- Execution engine. -----------------------------*)
+
+fun getCol (row : row) (col : columnref) =
+ Option.valOf (JSONUtil.findField row col)
+
+fun jsonEqual (JSON.INT x) (JSON.INT y) = x = y
+ | jsonEqual (JSON.STRING x) (JSON.STRING y) = x = y
+ | jsonEqual _ _ = raise Type
+
+fun equal row x y =
+ if x = y then true else
+ (case (x, y) of
+ ((String _), (Int _)) => raise Type
+ | ((Column c1), (Column c2)) => jsonEqual (getCol row c1) (getCol row c2)
+ | ((String x), (Column c)) => x = JSONUtil.asString (getCol row c)
+ | ((Int x), (Column c)) => x = JSONUtil.asInt (getCol row c)
+ | (x,y) => equal row y x)
+ handle Option => raise BadQuery
+
+fun greater row x y =
+ (case (x, y) of
+ ((Int x), (Int y)) => x > y
+ | ((Int x), (Column c)) => x > JSONUtil.asInt (getCol row c)
+ | ((Column c), (Int x)) => JSONUtil.asInt (getCol row c) > x
+ | ((Column c1), (Column c2)) => JSONUtil.asInt (getCol row c1) > JSONUtil.asInt (getCol row c2)
+ | _ => raise Type)
+ handle Option => raise BadQuery
+
+(* Given a predicate and a row, check if the row satisfies the predicate. *)
+fun check (Expr(bop)) row : bool =
+ (case bop of
+ Eq(x, y) => equal row x y
+ | Neq(x, y) => not (equal row x y)
+ | Gt(x, y) => greater row x y
+ | Lt(x, y) => not (greater row x y) andalso not (equal row x y))
+ | check (And(p1, p2)) row = check p1 row andalso check p2 row
+ | check (Or(p1, p2)) row = check p1 row orelse check p2 row
+
+fun subset A B = List.all (fn x => List.exists (fn y => x = y) B) A
+
+(* Returns list of all fields of JSON object, which given this challenge's
+ * assumptions should be the list of all columns in the table. *)
+fun getCols ((JSON.OBJECT r) : row) : columnref list = List.map (fn (name, _) => name) r
+ | getCols _ = raise MalformedData
+
+(* Optionally filters rows for those matching given predicate (if it exists). *)
+fun predFilter (SOME p) L = List.filter (fn r => check p r) L
+ | predFilter NONE L = L
+
+(* Optionally filters for the first n elements of a list. *)
+fun optTake (SOME n) L = List.take (L, n)
+ | optTake NONE L = L
+
+fun execute (Select(req, table, pred, lim)) : rowvals list * columnref list =
+ let
+ val fname = table ^ ".json"
+ val (r::rs) = (case JSONParser.parseFile fname of JSON.ARRAY x => x)
+ val cols = getCols r
+ val targets = (case req of All => cols | Columns(c) => c)
+ val () = if not (subset targets (getCols r)) then raise BadQuery else ()
+ in
+ (List.map (fn row => List.map (fn c => getCol row c) targets)
+ (optTake lim (predFilter pred (r::rs))),
+ targets)
+end handle Match => raise MalformedData
+
+(*--------------------------- Display utilities. -----------------------------*)
+
+(* Coerce JSON values in list of row values to string types *)
+fun stringifyRow (row : rowvals) =
+ List.map (fn (JSON.STRING x) => x
+ | (JSON.INT x) => IntInf.toString x) row
+
+(* Returns a list of the max widths of each columns for padding. *)
+fun getMaxSizes L = let
+ val rows = (map (fn x => map String.size x) L)
+in
+ List.foldr (fn (x,y) => map Int.max (ListPair.zip (x,y))) (hd rows) rows
+end
+
+(* Pad rows to align nicely when printed out. *)
+fun padRows rows = let
+ val maxs = getMaxSizes rows
+ val rec pad = (fn 0 => "" | n =>" " ^ pad (n-1))
+in
+ List.map (fn x => map (fn (x,y) => x ^ (pad (y - (String.size x))))
+ (ListPair.zip (x,maxs))) rows
+end
+
+(* Delimits a list of strings by a delimiter. *)
+fun delimit delim strings = List.foldr (fn (x, y) => x ^ delim ^ y) "" strings
+
+(* Given a set of rows and columns, pretty prints them to stdout. *)
+fun display ((rows, cols) : rowvals list * columnref list) =
+ (print o (delimit "\n") o (List.map (fn row => delimit " | " row)) o padRows)
+ (cols::(map stringifyRow rows))
+
+(* Main execution loop of program. *)
+fun loop () : unit =
+ let
+ val input = Option.valOf (TextIO.inputLine TextIO.stdIn)
+ handle Option => raise Parse
+ in
+ loop ((display o execute o parse) input
+ handle BadQuery => print "bad query\n"
+ | MalformedData => print "malformed data\n"
+ | Type => print "type error\n"
+ | Parse => print "parse error\n"
+ | Io => print "no such file\n")
+ end
+
+structure Main =
+struct
+fun main (_, _) = let
+ val () = loop ()
+in
+ OS.Process.success
+end
+end
diff --git a/randgen.py b/randgen.py
@@ -0,0 +1,30 @@
+
+# { "state": "Mexico", "region": "South", "pop": 2312312322, "pop_male": 3123123, "pop_female": 123123 }
+import json
+import random
+import urllib.request
+states = ['Alabama', 'Alaska', 'Arizona', 'Arkansas', 'California', 'Colorado', 'Connecticut', 'Delaware', 'Florida', 'Georgia', 'Hawaii', 'Idaho', 'Illinois', 'Indiana', 'Iowa', 'Kansas', 'Kentucky', 'Louisiana', 'Maine', 'Maryland', 'Massachusetts', 'Michigan', 'Minnesota', 'Mississippi', 'Missouri', 'Montana', 'Nebraska', 'Nevada', 'New Hampshire', 'New Jersey', 'New Mexico', 'New York', 'North Carolina', 'North Dakota', 'Ohio', 'Oklahoma', 'Oregon', 'Pennsylvania', 'Rhode Island', 'South Carolina', 'South Dakota', 'Tennessee', 'Texas', 'Utah', 'Vermont', 'Virginia', 'Washington', 'West Virginia', 'Wisconsin', 'Wyoming']
+regions = ["South", "West", "Southwest", "North", "East", "Northeast", "Middle", "Midwest", "Mideast", "Nowhere"]
+
+word_site = "https://www.mit.edu/~ecprice/wordlist.10000"
+response = urllib.request.urlopen(word_site)
+txt = response.read()
+WORDS = txt.splitlines()
+
+print(random.choice(states))
+
+# print(WORDS[:10])
+
+data = []
+for i in range(10000):
+ data.append({"state": random.choice(states),
+ "region": random.choice(regions),
+ "name": f"{random.choice(WORDS).decode().capitalize()} {random.choice(WORDS).decode().capitalize()}",
+ "pop": random.randint(1000000, 1000000000),
+ "pop_male": random.randint(10000, 1000000),
+ "pop_female": random.randint(10000, 1000000)})
+
+f = open("./cities.json", "w")
+f.write(json.dumps(data))
+f.close()
+
diff --git a/readme.md b/readme.md
@@ -0,0 +1,25 @@
+# minisql
+> simple sql querying over json files
+
+## install
+Run `install.sh` which will automatically install SML locally and compile `minisql`.
+
+## usage
+Run `./minisql` to run queries. No need for a command line argument: simply use the name of the JSON file you want to query as the name of the table in your query and `minisql` will parse it on the fly.
+
+You can generate some sample data to play with by running `randgen.py`. This will make a file called `cities.json` with randomized data.
+
+Example query (over the file `cities.json` in the current directory):
+```
+$ ./minisql
+SELECT * FROM cities WHERE (pop > 1000000 AND pop_male > 2) AND state != 'California' LIMIT 5;
+```
+which results in:
+```
+state | region | name | pop | pop_male | pop_female
+South Dakota | Midwest | Titanium Difficulties | 889974703 | 458536 | 250643
+Wisconsin | West | Idaho Montgomery | 428577562 | 764134 | 683030
+Georgia | Southwest | Glasgow Nudity | 35972038 | 44695 | 652128
+South Carolina | South | Handles Mineral | 260061223 | 515245 | 944841
+Delaware | North | Click Epa | 658863391 | 73868 | 451517
+```
