1before: | 2 global_table = "_G" 3 this_module = "std.tree" 4 5 Tree = require "std.tree" 6 7specify std.tree: 8- before: 9 prototype = (require "std.object").prototype 10 t = {foo="foo", fnord={branch={bar="bar", baz="baz"}}, quux="quux"} 11 tr = Tree (t) 12 13- context when required: 14 - context by name: 15 - it does not touch the global table: 16 expect (show_apis {added_to=global_table, by=this_module}). 17 to_equal {} 18 19 - context via the std module: 20 - it does not touch the global table: 21 expect (show_apis {added_to=global_table, by="std"}). 22 to_equal {} 23 24- describe construction: 25 - it constructs a new tree: 26 tr = Tree {} 27 expect (tr).not_to_be (Tree) 28 expect (prototype (tr)).to_be "Tree" 29 - it turns a table argument into a tree: 30 expect (prototype (Tree (t))).to_be "Tree" 31 - it does not turn table argument values into sub-Trees: 32 expect (prototype (tr["fnord"])).to_be "table" 33 - it understands branched nodes: 34 expect (tr).to_equal (Tree (t)) 35 expect (tr[{"fnord"}]).to_equal (t.fnord) 36 expect (tr[{"fnord", "branch", "bar"}]).to_equal (t.fnord.branch.bar) 37 - it serves as a prototype for new instances: 38 obj = tr {} 39 expect (prototype (obj)).to_be "Tree" 40 expect (obj).to_equal (tr) 41 expect (getmetatable (obj)).to_be (getmetatable (tr)) 42 43 44- describe clone: 45 - before: 46 subject = { k1 = {"v1"}, k2 = {"v2"}, k3 = {"v3"} } 47 f = Tree.clone 48 - it does not just return the subject: 49 expect (f (subject)).not_to_be (subject) 50 - it does copy the subject: 51 expect (f (subject)).to_equal (subject) 52 - it makes a deep copy: 53 expect (f (subject).k1).not_to_be (subject.k1) 54 - it does not perturb the original subject: 55 target = { k1 = subject.k1, k2 = subject.k2, k3 = subject.k3 } 56 copy = f (subject) 57 expect (subject).to_equal (target) 58 expect (subject).to_be (subject) 59 - it diagnoses non-table arguments: 60 expect (f ()).to_raise ("table expected") 61 expect (f "foo").to_raise ("table expected") 62 63 64- describe ileaves: 65 - before: 66 f = Tree.ileaves 67 l = {} 68 - it iterates over array part of a table argument: 69 for v in f {"first", "second", "3rd"} do l[1+#l]=v end 70 expect (l).to_equal {"first", "second", "3rd"} 71 - it iterates over array parts of nested table argument: 72 for v in f {{"one", {"two"}, {{"three"}, "four"}}, "five"} do 73 l[1+#l]=v 74 end 75 expect (l).to_equal {"one", "two", "three", "four", "five"} 76 - it skips hash part of a table argument: 77 for v in f {"first", "second"; third = "2rd"} do l[1+#l]=v end 78 expect (l).to_equal {"first", "second"} 79 - it skips hash parts of nested table argument: 80 for v in f {{"one", {two=2}, {{"three"}, four=4}}, foo="bar", "five"} do 81 l[1+#l]=v 82 end 83 expect (l).to_equal {"one", "three", "five"} 84 - it works on trees too: 85 for v in f (Tree {Tree {"one", 86 Tree {two=2}, 87 Tree {Tree {"three"}, four=4} 88 }, 89 foo="bar", "five"}) 90 do 91 l[1+#l]=v 92 end 93 expect (l).to_equal {"one", "three", "five"} 94 - it diagnoses non-table arguments: 95 expect (f ()).to_raise ("table expected") 96 expect (f "string").to_raise ("table expected") 97 98 99- describe inodes: 100 - before: | 101 f = Tree.inodes 102 local tostring = (require "std.string").tostring 103 104 function traverse (subject) 105 l = {} 106 for ty, p, n in f (subject) do 107 l[1+#l]={ty, Tree.clone (p), n} 108 end 109 return l 110 end 111 - it iterates over array part of a table argument: | 112 subject = {"first", "second", "3rd"} 113 expect (traverse (subject)). 114 to_equal {{"branch", {}, subject}, -- { 115 {"leaf", {1}, subject[1]}, -- first, 116 {"leaf", {2}, subject[2]}, -- second, 117 {"leaf", {3}, subject[3]}, -- 3rd, 118 {"join", {}, subject}} -- } 119 - it iterates over array parts of nested table argument: | 120 subject = {{"one", {"two"}, {{"three"}, "four"}}, "five"} 121 expect (traverse (subject)). 122 to_equal {{"branch", {}, subject}, -- { 123 {"branch", {1}, subject[1]}, -- { 124 {"leaf", {1,1}, subject[1][1]}, -- one, 125 {"branch", {1,2}, subject[1][2]}, -- { 126 {"leaf", {1,2,1}, subject[1][2][1]}, -- two, 127 {"join", {1,2}, subject[1][2]}, -- }, 128 {"branch", {1,3}, subject[1][3]}, -- { 129 {"branch", {1,3,1}, subject[1][3][1]}, -- { 130 {"leaf", {1,3,1,1}, subject[1][3][1][1]}, -- three, 131 {"join", {1,3,1}, subject[1][3][1]}, -- }, 132 {"leaf", {1,3,2}, subject[1][3][2]}, -- four, 133 {"join", {1,3}, subject[1][3]}, -- }, 134 {"join", {1}, subject[1]}, -- }, 135 {"leaf", {2}, subject[2]}, -- five, 136 {"join", {}, subject}} -- } 137 - it skips hash part of a table argument: | 138 subject = {"first", "second"; third = "3rd"} 139 expect (traverse (subject)). 140 to_equal {{"branch", {}, subject}, -- { 141 {"leaf", {1}, subject[1]}, -- first, 142 {"leaf", {2}, subject[2]}, -- second, 143 {"join", {}, subject}} -- } 144 - it skips hash parts of nested table argument: | 145 subject = {{"one", {two=2}, {{"three"}, four=4}}, foo="bar", "five"} 146 expect (traverse (subject)). 147 to_equal {{"branch", {}, subject}, -- { 148 {"branch", {1}, subject[1]}, -- { 149 {"leaf", {1,1}, subject[1][1]}, -- one, 150 {"branch", {1,2}, subject[1][2]}, -- { 151 {"join", {1,2}, subject[1][2]}, -- }, 152 {"branch", {1,3}, subject[1][3]}, -- { 153 {"branch", {1,3,1}, subject[1][3][1]}, -- { 154 {"leaf", {1,3,1,1}, subject[1][3][1][1]}, -- three, 155 {"join", {1,3,1}, subject[1][3][1]}, -- }, 156 {"join", {1,3}, subject[1][3]}, -- }, 157 {"join", {1}, subject[1]}, -- }, 158 {"leaf", {2}, subject[2]}, -- five, 159 {"join", {}, subject}} -- } 160 - it works on trees too: | 161 subject = Tree {Tree {"one", 162 Tree {two=2}, 163 Tree {Tree {"three"}, four=4}}, 164 foo="bar", 165 "five"} 166 expect (traverse (subject)). 167 to_equal {{"branch", {}, subject}, -- { 168 {"branch", {1}, subject[1]}, -- { 169 {"leaf", {1,1}, subject[1][1]}, -- one, 170 {"branch", {1,2}, subject[1][2]}, -- { 171 {"join", {1,2}, subject[1][2]}, -- }, 172 {"branch", {1,3}, subject[1][3]}, -- { 173 {"branch", {1,3,1}, subject[1][3][1]}, -- { 174 {"leaf", {1,3,1,1}, subject[1][3][1][1]}, -- three, 175 {"join", {1,3,1}, subject[1][3][1]}, -- }, 176 {"join", {1,3}, subject[1][3]}, -- }, 177 {"join", {1}, subject[1]}, -- }, 178 {"leaf", {2}, subject[2]}, -- five, 179 {"join", {}, subject}} -- } 180 - it diagnoses non-table arguments: 181 expect (f ()).to_raise ("table expected") 182 expect (f "string").to_raise ("table expected") 183 184 185- describe leaves: 186 - before: 187 f = Tree.leaves 188 l = {} 189 - it iterates over elements of a table argument: 190 for v in f {"first", "second", "3rd"} do l[1+#l]=v end 191 expect (l).to_equal {"first", "second", "3rd"} 192 - it iterates over elements of a nested table argument: 193 for v in f {{"one", {"two"}, {{"three"}, "four"}}, "five"} do 194 l[1+#l]=v 195 end 196 expect (l).to_equal {"one", "two", "three", "four", "five"} 197 - it includes the hash part of a table argument: 198 for v in f {"first", "second"; third = "3rd"} do l[1+#l]=v end 199 expect (l).to_equal {"first", "second", "3rd"} 200 - it includes hash parts of a nested table argument: 201 for v in f {{"one", {two=2}, {{"three"}, four=4}}, foo="bar", "five"} do 202 l[1+#l]=v 203 end 204 expect (l).to_contain. 205 a_permutation_of {"one", 2, "three", 4, "bar", "five"} 206 - it works on trees too: 207 for v in f (Tree {Tree {"one", 208 Tree {two=2}, 209 Tree {Tree {"three"}, four=4} 210 }, 211 foo="bar", "five"}) 212 do 213 l[1+#l]=v 214 end 215 expect (l).to_contain. 216 a_permutation_of {"one", 2, "three", 4, "bar", "five"} 217 - it diagnoses non-table arguments: 218 expect (f ()).to_raise ("table expected") 219 expect (f "string").to_raise ("table expected") 220 221 222- describe merge: 223 - before: | 224 f = Tree.merge 225 226 -- Additional merge keys which are moderately unusual 227 t1 = Tree { k1 = "v1", k2 = "if", k3 = Tree {"?"} } 228 t2 = Tree { ["if"] = true, [{"?"}] = false, _ = "underscore", k3 = "v2" } 229 230 target = Tree.clone (t1) 231 for ty, p, n in Tree.nodes (t2) do 232 if ty == "leaf" then target[p] = n end 233 end 234 - it does not create a whole new table: 235 expect (f (t1, t2)).to_be (t1) 236 - it does not change t1 when t2 is empty: 237 expect (f (t1, Tree {})).to_be (t1) 238 - it copies t2 when t1 is empty: | 239 expect (f (Tree {}, t1)).to_copy (t1) 240 - it merges keys from t2 into t1: | 241 expect (f (t1, t2)).to_equal (target) 242 - it gives precedence to values from t2: 243 original = Tree.clone (t1) 244 m = f (t1, t2) -- Merge is destructive, do it once only. 245 expect (m.k3).to_be (t2.k3) 246 expect (m.k3).not_to_be (original.k3) 247 - it diagnoses non-table arguments: 248 expect (f (nil, {})).to_raise ("table expected") 249 expect (f ({}, nil)).to_raise ("table expected") 250 251 252- describe nodes: 253 - before: 254 f = Tree.nodes 255 256 function traverse (subject) 257 l = {} 258 for ty, p, n in f (subject) do l[1+#l]={ty, Tree.clone (p), n} end 259 return l 260 end 261 - it iterates over the elements of a table argument: | 262 subject = {"first", "second", "3rd"} 263 expect (traverse (subject)). 264 to_equal {{"branch", {}, subject}, -- { 265 {"leaf", {1}, subject[1]}, -- first, 266 {"leaf", {2}, subject[2]}, -- second, 267 {"leaf", {3}, subject[3]}, -- 3rd, 268 {"join", {}, subject}} -- } 269 - it iterates over the elements of nested a table argument: | 270 subject = {{"one", {"two"}, {{"three"}, "four"}}, "five"} 271 expect (traverse (subject)). 272 to_equal {{"branch", {}, subject}, -- { 273 {"branch", {1}, subject[1]}, -- { 274 {"leaf", {1,1}, subject[1][1]}, -- one, 275 {"branch", {1,2}, subject[1][2]}, -- { 276 {"leaf", {1,2,1}, subject[1][2][1]}, -- two, 277 {"join", {1,2}, subject[1][2]}, -- }, 278 {"branch", {1,3}, subject[1][3]}, -- { 279 {"branch", {1,3,1}, subject[1][3][1]}, -- { 280 {"leaf", {1,3,1,1}, subject[1][3][1][1]}, -- three, 281 {"join", {1,3,1}, subject[1][3][1]}, -- }, 282 {"leaf", {1,3,2}, subject[1][3][2]}, -- four, 283 {"join", {1,3}, subject[1][3]}, -- }, 284 {"join", {1}, subject[1]}, -- }, 285 {"leaf", {2}, subject[2]}, -- five, 286 {"join", {}, subject}} -- } 287 - it includes the hash part of a table argument: | 288 -- like `pairs`, `nodes` can visit elements in any order, so we cannot 289 -- guarantee the array part is always visited before the hash part, or 290 -- even that the array elements are visited in order! 291 subject = {"first", "second"; third = "3rd"} 292 expect (traverse (subject)).to_contain. 293 a_permutation_of {{"branch", {}, subject}, -- { 294 {"leaf", {1}, subject[1]}, -- first, 295 {"leaf", {2}, subject[2]}, -- second, 296 {"leaf", {"third"}, subject["third"]}, -- 3rd 297 {"join", {}, subject}} -- } 298 - it includes hash parts of a nested table argument: | 299 -- like `pairs`, `nodes` can visit elements in any order, so we cannot 300 -- guarantee the array part is always visited before the hash part, or 301 -- even that the array elements are visited in order! 302 subject = {{"one", {two=2}, {{"three"}, four=4}}, foo="bar", "five"} 303 expect (traverse (subject)).to_contain. 304 a_permutation_of {{"branch", {}, subject}, -- { 305 {"branch", {1}, subject[1]}, -- { 306 {"leaf", {1,1}, subject[1][1]}, -- one, 307 {"branch", {1,2}, subject[1][2]}, -- { 308 {"leaf", {1,2,"two"}, subject[1][2]["two"]}, -- 2, 309 {"join", {1,2}, subject[1][2]}, -- }, 310 {"branch", {1,3}, subject[1][3]}, -- { 311 {"branch", {1,3,1}, subject[1][3][1]}, -- { 312 {"leaf", {1,3,1,1}, subject[1][3][1][1]}, -- three, 313 {"join", {1,3,1}, subject[1][3][1]}, -- }, 314 {"leaf", {1,3,"four"}, subject[1][3]["four"]}, -- 4, 315 {"join", {1,3}, subject[1][3]}, -- }, 316 {"join", {1}, subject[1]}, -- }, 317 {"leaf", {2}, subject[2]}, -- five, 318 {"leaf", {"foo"}, subject["foo"]}, -- bar, 319 {"join", {}, subject}} -- } 320 - it works on trees too: | 321 -- like `pairs`, `nodes` can visit elements in any order, so we cannot 322 -- guarantee the array part is always visited before the hash part, or 323 -- even that the array elements are visited in order! 324 subject = Tree {Tree {"one", 325 Tree {two=2}, 326 Tree {Tree {"three"}, four=4}}, 327 foo="bar", 328 "five"} 329 expect (traverse (subject)).to_contain. 330 a_permutation_of {{"branch", {}, subject}, -- { 331 {"branch", {1}, subject[1]}, -- { 332 {"leaf", {1,1}, subject[1][1]}, -- one, 333 {"branch", {1,2}, subject[1][2]}, -- { 334 {"leaf", {1,2,"two"}, subject[1][2]["two"]}, -- 2, 335 {"join", {1,2}, subject[1][2]}, -- }, 336 {"branch", {1,3}, subject[1][3]}, -- { 337 {"branch", {1,3,1}, subject[1][3][1]}, -- { 338 {"leaf", {1,3,1,1}, subject[1][3][1][1]}, -- three, 339 {"join", {1,3,1}, subject[1][3][1]}, -- }, 340 {"leaf", {1,3,"four"}, subject[1][3]["four"]}, -- 4, 341 {"join", {1,3}, subject[1][3]}, -- }, 342 {"join", {1}, subject[1]}, -- }, 343 {"leaf", {2}, subject[2]}, -- five, 344 {"leaf", {"foo"}, subject["foo"]}, -- bar, 345 {"join", {}, subject}} -- } 346 - it generates path key-lists that are valid __index arguments: | 347 subject = Tree {"first", Tree {"second"}, "3rd"} 348 expect (traverse (subject)). 349 to_equal {{"branch", {}, subject[{}]}, -- { 350 {"leaf", {1}, subject[{1}]}, -- first, 351 {"branch", {2}, subject[{2}]}, -- { 352 {"leaf", {2,1}, subject[{2,1}]}, -- second 353 {"join", {2}, subject[{2}]}, -- } 354 {"leaf", {3}, subject[{3}]}, -- 3rd, 355 {"join", {}, subject[{}]}} -- } 356 - it diagnoses non-table arguments: 357 expect (f ()).to_raise ("table expected") 358 expect (f "string").to_raise ("table expected") 359 360 361- describe __index: 362 - it returns nil for a missing key: 363 expect (tr["no such key"]).to_be (nil) 364 - it returns nil for missing single element key lists: 365 expect (tr[{"no such key"}]).to_be (nil) 366 - it returns nil for missing multi-element key lists: 367 expect (tr[{"fnord", "foo"}]).to_be (nil) 368 expect (tr[{"no", "such", "key"}]).to_be (nil) 369 - it returns a value for the given key: 370 expect (tr["foo"]).to_be "foo" 371 expect (tr["quux"]).to_be "quux" 372 - it returns tree root for empty key list: 373 expect (tr[{}]).to_be (tr) 374 - it returns values for single element key lists: 375 expect (tr[{"foo"}]).to_be "foo" 376 expect (tr[{"quux"}]).to_be "quux" 377 - it returns values for multi-element key lists: 378 expect (tr[{"fnord", "branch", "bar"}]).to_be "bar" 379 expect (tr[{"fnord", "branch", "baz"}]).to_be "baz" 380 381 382- describe __newindex: 383 - before: 384 tr = Tree {} 385 - it stores values for simple keys: 386 tr["foo"] = "foo" 387 expect (tr).to_equal (Tree {foo="foo"}) 388 - it stores values for single element key lists: 389 tr[{"foo"}] = "foo" 390 expect (tr).to_equal (Tree {foo="foo"}) 391 - it stores values for multi-element key lists: 392 tr[{"foo", "bar"}] = "baz" 393 expect (tr).to_equal (Tree {foo=Tree {bar="baz"}}) 394 - it separates branches for diverging key lists: 395 tr[{"foo", "branch", "bar"}] = "leaf1" 396 tr[{"foo", "branch", "baz"}] = "leaf2" 397 expect (tr).to_equal (Tree {foo=Tree {branch=Tree {bar="leaf1", baz="leaf2"}}}) 398 399- describe __tostring: 400 - it returns a string: 401 expect (prototype (tostring (tr))).to_be "string" 402 - it shows the type name: 403 expect (tostring (tr)).to_contain "Tree" 404 - it shows the contents in order: | 405 tr = Tree {foo = "foo", 406 fnord = Tree {branch = Tree {bar="bar", baz="baz"}}, 407 quux = "quux"} 408 expect (tostring (tr)). 409 to_contain 'fnord=Tree {branch=Tree {bar=bar, baz=baz}}, foo=foo, quux=quux' 410