doc/todo/allow_plugins_to_add_sorting_methods.mdwn

   1 [[!tag patch]]
   2
   3 The available [[ikiwiki/pagespec/sorting]] methods are currently hard-coded in
   4 IkiWiki.pm, making it difficult to add any extra sorting mechanisms. I've
   5 prepared a branch which adds 'sort' as a hook type and uses it to implement a
   6 new `meta_title` sort type.
   7
   8 Someone could use this hook to make `\[[!inline sort=title]]` prefer the meta
   9 title over the page name, but for compatibility, I'm not going to (I do wonder
  10 whether it would be worth making sort=name an alias for the current sort=title,
  11 and changing the meaning of sort=title in 4.0, though).
  12
  13 > What compatability concerns, exactly, are there that prevent making that
  14 > change now? --[[Joey]]
  15
  16 *[sort-hooks branch now withdrawn in favour of sort-package --s]*
  17
  18 I briefly tried to turn *all* the current sort types into hook functions, and
  19 have some of them pre-registered, but decided that probably wasn't a good idea.
  20 That earlier version of the branch is also available for comparison:
  21
  22 *[also withdrawn in favour of sort-package --s]*
  23
  24 >> I wonder if IkiWiki would benefit from the concept of a "sortspec", like a [[ikiwiki/PageSpec]] but dedicated to sorting lists of pages rather than defining lists of pages?  Rather than defining a sort-hook, define a SortSpec class, and enable people to add their own sort methods as functions defined inside that class, similarly to the way they can add their own pagespec definitions. --[[KathrynAndersen]]
  25
  26 >>> [[!template id=gitbranch branch=smcv/ready/sort-package author="[[Simon_McVittie|smcv]]"]]
  27 >>> I'd be inclined to think that's overkill, but it wasn't very hard to
  28 >>> implement, and in a way is more elegant. I set it up so sort mechanisms
  29 >>> share the `IkiWiki::PageSpec` package, but with a `cmp_` prefix. Gitweb:
  30 >>> <http://git.pseudorandom.co.uk/smcv/ikiwiki.git?a=shortlog;h=refs/heads/sort-package>
  31
  32 >>>> I agree it seems more elegant, so I have focused on it.
  33 >>>>
  34 >>>> I don't know about reusing `IkiWiki::PageSpec` for this.
  35 >>>> --[[Joey]]
  36
  37 >>>>> Fair enough, `IkiWiki::SortSpec::cmp_foo` would be just
  38 >>>>> as easy, or `IkiWiki::Sorting::cmp_foo` if you don't like
  39 >>>>> introducing "sort spec" in the API. I took a cue from
  40 >>>>> [[ikiwiki/pagespec/sorting]] being a subpage of
  41 >>>>> [[ikiwiki/pagespec]], and decided that yes, sorting is
  42 >>>>> a bit like a pagespec :-) Which name would you prefer? --s
  43
  44 >>>>>> `SortSpec` --[[Joey]]
  45
  46 >>>>>>> [[Done]]. --s
  47
  48 >>>> I would be inclined to drop the `check_` stuff. --[[Joey]]
  49
  50 >>>>> It basically exists to support `title_natural`, to avoid
  51 >>>>> firing up the whole import mechanism on every `cmp`
  52 >>>>> (although I suppose that could just be a call to a
  53 >>>>> memoized helper function). It also lets sort specs that
  54 >>>>> *must* have a parameter, like
  55 >>>>> [[field|plugins/contrib/field/discussion]], fail early
  56 >>>>> (again, not so valuable).
  57 >>>>>
  58 >>>>>> AFAIK, `use foo` has very low overhead when the module is already
  59 >>>>>> loaded. There could be some evalation overhead in `eval q{use foo}`,
  60 >>>>>> if so it would be worth addressing across the whole codebase.
  61 >>>>>> --[[Joey]]
  62 >>>>>>
  63 >>>>>>> check_cmp_foo now dropped. --s
  64 >>>>>
  65 >>>>> The former function could be achieved at a small
  66 >>>>> compatibility cost by putting `title_natural` in a new
  67 >>>>> `sortnatural` plugin (that fails to load if you don't
  68 >>>>> have `title_natural`), if you'd prefer - that's what would
  69 >>>>> have happened if `title_natural` was written after this
  70 >>>>> code had been merged, I suspect. Would you prefer this? --s
  71
  72 >>>>>> Yes! (Assuming it does not make sense to support
  73 >>>>>> natural order sort of other keys than the title, at least..)
  74 >>>>>>  --[[Joey]]
  75
  76 >>>>>>> Done. I added some NEWS.Debian for it, too. --s
  77
  78 >>>> Wouldn't it make sense to have `meta(title)` instead
  79 >>>> of `meta_title`? --[[Joey]]
  80
  81 >>>>> Yes, you're right. I added parameters to support `field`,
  82 >>>>> and didn't think about making `meta` use them too.
  83 >>>>> However, `title` does need a special case to make it
  84 >>>>> default to the basename instead of the empty string.
  85 >>>>>
  86 >>>>> Another special case for `title` is to use `titlesort`
  87 >>>>> first (the name `titlesort` is derived from Ogg/FLAC
  88 >>>>> tags, which can have `titlesort` and `artistsort`).
  89 >>>>> I could easily extend that to other metas, though;
  90 >>>>> in fact, for e.g. book lists it would be nice for
  91 >>>>> `field(bookauthor)` to behave similarly, so you can
  92 >>>>> display "Douglas Adams" but sort by "Adams, Douglas".
  93 >>>>>
  94 >>>>> `meta_title` is also meant to be a prototype of how
  95 >>>>> `sort=title` could behave in 4.0 or something - sorting
  96 >>>>> by page name (which usually sorts in approximately the
  97 >>>>> same place as the meta-title, but occasionally not), while
  98 >>>>> displaying meta-titles, does look quite odd. --s
  99
 100 >>>>>> Agreed. --[[Joey]]
 101
 102 >>>>>>> I've implemented meta(title). meta(author) also has the
 103 >>>>>>> `sortas` special case; meta(updated) and meta(date)
 104 >>>>>>> should also work how you'd expect them to (but they're
 105 >>>>>>> earliest-first, unlike age). --s
 106
 107 >>>> As I read the regexp in `cmpspec_translate`, the "command"
 108 >>>> is required to have params. They should be optional,
 109 >>>> to match the documentation and because most sort methods
 110 >>>> do not need parameters. --[[Joey]]
 111
 112 >>>>> No, `$2` is either `\w+\([^\)]*\)` or `[^\s]+` (with the
 113 >>>>> latter causing an error later if it doesn't also match `\w+`).
 114 >>>>> This branch doesn't add any parameterized sort methods,
 115 >>>>> in fact, although I did provide one on
 116 >>>>> [[field's_discussion_page|plugins/contrib/report/discussion]]. --s
 117
 118 >>>> I wonder if it would make sense to add some combining keywords, so
 119 >>>> a sortspec reads like `sort="age then ascending title"`
 120 >>>> In a way, this reduces the amount of syntax that needs to be learned.
 121 >>>> I like the "then" (and it could allow other operations than
 122 >>>> simple combination, if any others make sense). Not so sure about the
 123 >>>> "ascending", which could be "reverse" instead, but "descending age" and
 124 >>>> "ascending age" both seem useful to be able to explicitly specify.
 125 >>>> --[[Joey]]
 126
 127 >>>>> Perhaps. I do like the simplicity of [[KathrynAndersen]]'s syntax
 128 >>>>> from [[plugins/contrib/report]] (which I copied verbatim, except for
 129 >>>>> turning sort-by-`field` into a parameterized spec).
 130 >>>>>
 131 >>>>> If we're getting into English-like (or at least SQL-like) queries,
 132 >>>>> it might make sense to change the signature of the hook function
 133 >>>>> so it's a function to return a key, e.g.
 134 >>>>> `sub key_age { return -%pagemtime{$_[0]) }`. Then we could sort like
 135 >>>>> this:
 136 >>>>>
 137 >>>>>     field(artistsort) or field(artist) or constant(Various Artists) then meta(titlesort) or meta(title) or title
 138 >>>>>
 139 >>>>> with "or" binding more closely than "then". Does this seem valuable?
 140 >>>>> I think the implementation would be somewhat more difficult. and
 141 >>>>> it's probably getting too complicated to be worthwhile, though?
 142 >>>>> (The keys that actually benefit from this could just
 143 >>>>> have smarter cmp functions, I think.)
 144 >>>>>
 145 >>>>> If the hooks return keys rather than cmp results, then we could even
 146 >>>>> have "lowercase" as an adjective used like "ascending"... maybe.
 147 >>>>> However, there are two types of adjective here: "lowercase"
 148 >>>>> really applies to the keys, whereas "ascending" applies to the "cmp"
 149 >>>>> result. Again, I think this is getting too complex, and could just
 150 >>>>> be solved with smarter cmp functions.
 151 >>>>>
 152 >>>>>> I agree. (Also, I think returning keys may make it harder to write
 153 >>>>>> smarter cmp functions.) --[[Joey]]
 154 >>>>>
 155 >>>>> Unfortunately, `sort="ascending mtime"` actually sorts by *descending*
 156 >>>>> timestamp (but`sort=age` is fine, because `age` could be defined as
 157 >>>>> now minus `ctime`). `sort=freshness` isn't right either, because
 158 >>>>> "sort by freshness" seems as though it ought to mean freshest first,
 159 >>>>> but "sort by ascending freshness" means put the least fresh first. If
 160 >>>>> we have ascending and descending keywords which are optional, I don't
 161 >>>>> think we really want different sort types to have different default
 162 >>>>> directions - it seems clearer to have `ascending` always be a no-op,
 163 >>>>> and `descending` always negate.
 164 >>>>>
 165 >>>>>> I think you've convinced me that ascending/descending impose too
 166 >>>>>> much semantics on it, so "-" is better. --[[Joey]]
 167
 168 >>>>>>> I've kept the semantics from `report` as-is, then:
 169 >>>>>>> e.g. `sort="age -title"`. --s
 170
 171 >>>>> Perhaps we could borrow from `meta updated` and use `update_age`?
 172 >>>>> `updateage` would perhaps be a more normal IkiWiki style - but that
 173 >>>>> makes me think that updateage is a quantity analagous to tonnage or
 174 >>>>> voltage, with more or less recently updated pages being said to have
 175 >>>>> more or less updateage. I don't know whether that's good or bad :-)
 176 >>>>>
 177 >>>>> I'm sure there's a much better word, but I can't see it. Do you have
 178 >>>>> a better idea? --s
 179
 180 [Regarding the `meta title=foo sort=bar` special case]
 181
 182 > I feel it sould be clearer to call that "sortas", since "sort=" is used
 183 > to specify a sort method in other directives. --[[Joey]]
 184 >> Done. --[[smcv]]
 185
 186 ## speed
 187
 188 I notice the implementation does not use the magic `$a` and `$b` globals.
 189 That nasty perl optimisation is still worthwhile:
 190
 191         perl -e 'use warnings; use strict; use Benchmark; sub a { $a <=> $b } sub b ($$) { $_[0] <=> $_[1] }; my @list=reverse(1..9999); timethese(10000, {a => sub {my @f=sort a @list}, b => sub {my @f=sort b  @list}, c => => sub {my @f=sort { b($a,$b) } @list}})'
 192         Benchmark: timing 10000 iterations of a, b, c...
 193                  a: 80 wallclock secs (76.74 usr +  0.05 sys = 76.79 CPU) @ 130.23/s (n=10000)
 194                  b: 112 wallclock secs (106.14 usr +  0.20 sys = 106.34 CPU) @ 94.04/s (n=10000)
 195                  c: 330 wallclock secs (320.25 usr +  0.17 sys = 320.42 CPU) @ 31.21/s (n=10000)
 196
 197 Unfortunatly, I think that c is closest to the new implementation.
 198 --[[Joey]]
 199
 200 > Unfortunately, `$a` isn't always `$main::a` - it's `$Package::a` where
 201 > `Package` is the call site of the sort call. This was a showstopper when
 202 > `sort` was a hook implemented in many packages, but now that it's a
 203 > `SortSpec`, I may be able to fix this by putting a `sort` wrapper in the
 204 > `SortSpec` namespace, so it's like this:
 205 >
 206 >     sub sort ($@)
 207 >     {
 208 >         my $cmp = shift;
 209 >         return sort $cmp @_;
 210 >     }
 211 >
 212 > which would mean that the comparison used `$IkiWiki::SortSpec::a`.
 213 > --s
 214
 215 >> I've now done this. On a wiki with many [[plugins/contrib/album]]s
 216 >> (a full rebuild takes half an hour!), I tested a refresh after
 217 >> `touch tags/*.mdwn` (my tag pages contain inlines of the form
 218 >> `tagged(foo)` sorted by date, so they exercise sorting).
 219 >> I also tried removing sorting from `pagespec_match_list`
 220 >> altogether, as an upper bound for how fast we can possibly make it.
 221 >>
 222 >> * `master` at branch point: 63.72user 0.29system
 223 >> * `master` at branch point: 63.91user 0.37system
 224 >> * my branch, with `@_`: 65.28user 0.29system
 225 >> * my branch, with `@_`: 65.21user 0.28system
 226 >> * my branch, with `$a`: 64.09user 0.28system
 227 >> * my branch, with `$a`: 63.83user 0.36system
 228 >> * not sorted at all: 58.99user 0.29system
 229 >> * not sorted at all: 58.92user 0.29system
 230 >>
 231 >> --s
 232
 233 > I do notice that `pagespec_match_list` performs the sort before the
 234 > filter by pagespec. Is this a deliberate design choice, or
 235 > coincidence? I can see that when `limit` is used, this could be
 236 > used to only run the pagespec match function until `limit` pages
 237 > have been selected, but the cost is that every page in the wiki
 238 > is sorted. Or, it might be useful to do the filtering first, then
 239 > sort the sub-list thus produced, then finally apply the limit? --s
 240
 241 >> Yes, it was deliberate, pagespec matching can be expensive enough that
 242 >> needing to sort a lot of pages seems likely to be less work. (I don't
 243 >> remember what benchmarking was done though.) --[[Joey]]
 244
 245 >>> We discussed this on IRC and Joey pointed out that this also affects
 246 >>> dependency calculation, so I'm not going to get into this now... --s
 247
 248 Joey pointed out on IRC that the `titlesort` feature duplicates all the
 249 meta titles. I did that in order to sort by the unescaped version, but
 250 I've now changed the branch to only store that if it makes a difference.
 251 --s
 252
 253 ## Documentation from sort-package branch
 254
 255 ### advanced sort orders (conditionally added to [[ikiwiki/pagespec/sorting]])
 256
 257 * `title_natural` - Orders by title, but numbers in the title are treated
 258   as such, ("1 2 9 10 20" instead of "1 10 2 20 9")
 259 * `meta(title)` - Order according to the `\[[!meta title="foo" sortas="bar"]]`
 260   or `\[[!meta title="foo"]]` [[ikiwiki/directive]], or the page name if no
 261   full title was set. `meta(author)`, `meta(date)`, `meta(updated)`, etc.
 262   also work.
 263
 264 ### Multiple sort orders (added to [[ikiwiki/pagespec/sorting]])
 265
 266 In addition, you can combine several sort orders and/or reverse the order of
 267 sorting, with a string like `age -title` (which would sort by age, then by
 268 title in reverse order if two pages have the same age).
 269
 270 ### meta sortas parameter (added to [[ikiwiki/directive/meta]])
 271
 272 [in title]
 273
 274 An optional `sort` parameter will be used preferentially when
 275 [[ikiwiki/pagespec/sorting]] by `meta(title)`:
 276
 277        \[[!meta title="The Beatles" sort="Beatles, The"]]
 278
 279        \[[!meta title="David Bowie" sort="Bowie, David"]]
 280
 281 [in author]
 282
 283   An optional `sortas` parameter will be used preferentially when
 284   [[ikiwiki/pagespec/sorting]] by `meta(author)`:
 285
 286         \[[!meta author="Joey Hess" sortas="Hess, Joey"]]
 287
 288 ### Sorting plugins (added to [[plugins/write]])
 289
 290 Similarly, it's possible to write plugins that add new functions as
 291 [[ikiwiki/pagespec/sorting]] methods. To achieve this, add a function to
 292 the IkiWiki::SortSpec package named `cmp_foo`, which will be used when sorting
 293 by `foo` or `foo(...)` is requested.
 294
 295 The names of pages to be compared are in the global variables `$a` and `$b`
 296 in the IkiWiki::SortSpec package. The function should return the same thing
 297 as Perl's `cmp` and `<=>` operators: negative if `$a` is less than `$b`,
 298 positive if `$a` is greater, or zero if they are considered equal. It may
 299 also raise an error using `error`, for instance if it needs a parameter but
 300 one isn't provided.
 301
 302 The function will also be passed one or more parameters. The first is
 303 `undef` if invoked as `foo`, or the parameter `"bar"` if invoked as `foo(bar)`;
 304 it may also be passed additional, named parameters.