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