- ikiwiki (3.14159266) UNRELEASED; urgency=low
++ikiwiki (3.2009XXXX) UNRELEASED; urgency=low
+
- * parentlinks: Add has_parentlinks template parameter to allow styling
- the toplevel index differently etc.
- * img: Correct bug in image size calculation code.
- * img: Fix dependency code for full size images.
- * toggle, relativedate: Support templates that add attributes
- to the body tag.
- * Support RPC::XML 0.69's incompatable object instantiation method.
- * mirrorlist: Display nothing if list is empty.
- * Fix a bug that could lead to duplicate links being recorded
- for tags.
- * Added support framework for multiple types of dependencies.
- * Allow declaring that a dependency is only affected by page presence
- or changes to its links.
++ * Added support framework for multiple types of dependencies, including
++ dependncies that are only affected by page precence or link changes.
++ * Rebuild wikis on upgrade to this version to get improved dependency
++ info.
+ * pagecount, calendar, postsparkline, progress: Use a presence dependency,
+ which makes these directives much less expensive to use, since page
+ edits will no longer trigger an unnecessary update.
+ * map: Use a presence dependency unless show= is specified.
+ This makes maps efficient enough that they can be used on sidebars!
+ * inline: Use a presence dependency in quick mode.
+ * brokenlinks: Use a link dependency.
+ This makes it much more efficient, only updating when really necessary.
+ * orphans, pagestats: Use a combination of presence and link dependencies.
+ This makes them more efficient. It also fixes a longstanding bug,
+ where if only a small set of pages were considered by orphans/pagestats,
+ changes to links on other pages failed to cause an update.
+ * linkmap: Use a combination of presence and link dependencies.
+ This makes the map be regenerated much less frequently in many cases,
+ so larger maps are more practical to use now.
- * Transitive dependencies are now correctly supported.
- * Rebuild wikis on upgrade to this version to get improved dependency
- info.
+ * Plugins providing PageSpec `match_*` functions should pass additional
- influence information when creating result objects.
++ influence information when creating result objects. This allows correctly
++ handling many more complicated dependencies.
+ * API change: `pagespec_match_list` has completly changed its interface.
+ The old interface will be removed soon, and a warning will be printed
+ if any plugins try to use it.
++ * Transitive dependencies are now correctly supported.
++
++ -- Joey Hess <joeyh@debian.org> Fri, 09 Oct 2009 20:13:27 -0400
++
+ ikiwiki (3.20091009) unstable; urgency=low
+
+ * parentlinks: Add has_parentlinks template parameter to allow styling
+ the toplevel index differently etc.
+ * img: Correct bug in image size calculation code.
+ * img: Fix dependency code for full size images.
+ * toggle, relativedate: Support templates that add attributes
+ to the body tag.
+ * Support RPC::XML 0.69's incompatible object instantiation method.
+ * mirrorlist: Display nothing if list is empty.
+ * Fix a bug that could lead to duplicate links being recorded
+ for tags.
- * Optimize away most expensive file prune calls, when refreshing,
+ * Optimize away most expensive file prune checks, when refreshing,
by only checking new files.
- -- Joey Hess <joeyh@debian.org> Sun, 27 Sep 2009 17:40:03 -0400
+ -- Joey Hess <joeyh@debian.org> Fri, 09 Oct 2009 19:53:50 -0400
ikiwiki (3.14159265) unstable; urgency=low
modification to plugins/brokenlinks causes an unnecessary update of
plugins, and could be solved by adding more dependency types.)
---[[Joey]]
+[[done]] --[[Joey]]
+
+ > Some questions/comments... I've thought about this a lot for [[todo/tracking_bugs_with_dependencies]].
+ >
+ > * When you say that anything that causes a rebuild of B is treated as a change of B, are you: i) Treating
+ > any rebuild as a change, or ii) Treating any rebuild that gives a new result as a change? Option ii) would
+ > lead to fewer rebuilds. Implementation is easy: when you're about to rebuild a page, load the old rendered html in. Do the rebuild. Compare
+ > the new and old html. If there is a difference, then mark that page as having changed. If there is no difference
+ > then you don't need to mark that pages as changed, even though it has been rebuilt. (This would ignore pages in meta-data that don't
+ > cause changes in html, but I don't think that is a huge issue.)
+
+ >> That is a good idea. I will have to look at it to see if the overhead of
+ >> reading back in the html of every page before building actually is a
+ >> win though. So far, I've focused on avoiding unnecessary rebuilds, and
+ >> there is still some room for more dependency types doing so.
+ >> (Particularly for metadata dependencies..) --[[Joey]]
+
+ > * The second comment I have relates to cycles in transitive dependencies. At the moment I don't think this is
+ > possible, but with some additions it may well become so. This could be problematic as it could lead to a)
+ > updates that never complete, or b) it being theoretically unclear what the final result should be (i.e. you
+ > can construct logical paradoxes in the system). I think the point above about marking things as changed only when
+ > the output actually changes fixes any cases that are well defined. For logical paradoxes and infinite loops (e.g.
+ > two pages that include each other), you might want to put a limit on the number of times you'll rebuild a page in any
+ > given run of ikiwiki. Say, only allow a page to rebuild twice on any run, regardless of whether a page it depends on changes.
+ > This is not a perfect solution, but would be a good approximation. -- [[Will]]
+
+ >> Ikiwiki only builds any given output file once per run, already. --[[Joey]]
>>>>> like that would probably not support what you want to do.
>>>>> --[[Joey]]
+ >>>>>> Yes - that's what I'm talking about - I'll add some comments there. -- [[Will]]
+
----
### Link dependencies
that the page links to, which is just what link dependencies are
triggered on.
+[[done]]
----
### the removal problem
> Trying to make a formal definition of this: (Note, I'm using the term sets rather than lists, but they're roughly equivalent)
>
> * Let the *matching set* for a pagespec be the set of existing pages that the pagespec matches.
- > * Let a *influence set* for a pagespec be the set of all pages, *p*, whose alteration might:
+ > * Let the *missing document matching set* be the set of pages that would match the spec if they didn't exist. These pages may or may not currently exist. Note that membership of this set depends upon how the `match_()` functions react to non-existant pages.
+ > * Let the *indirect influence set* for a pagespec be the set of all pages, *p*, whose alteration might:
> * cause the pagespec to include or exclude a page other than *p*, or
- > * cause the pagespec to exclude *p*.
+ > * cause the pagespec to exclude *p*, unless the alteration is the removal of *p* and *p* is in the missing document matching set.
+ >
+ > Justification: The 'base dependency mechanism' is to compare changed pages against each pagespec. If the page matches, then rebuild the spec. For this comparison, creation and removal
+ > of pages are both considered changes. This base mechanism will catch:
+ >
+ > * The addition of any page to the matching set through its own modification/creation
+ > * The removal of any page *that would still match while non-existant* from the matching set through its own removal. (Note: The base mechanism cannot remove a page from the matching set because of that page's own modification (not deletion). If the page should be removed matching set, then it obviously cannot match the spec after the change.)
+ > * The modification (not deletion) of any page that still matches after the modification.
>
- >> \[Will snipped some stuff and edited the formal definition]
+ > The base mechanism may therefore not catch:
+ >
+ > * The addition or removal of any page from the matching set through the modification/addition/removal of any other page.
+ > * The removal of any page from the matching set through its own modification/removal if it does not still match after the change.
+ >
+ > The indirect influence set then should handle anything that the base mechanism will not catch.
>
> --[[Will]]
#### Examples
- * The pagespec "created_before(foo)" has an influence list that contains foo.
+ * The pagespec "created_before(foo)" has an indirect influence list that contains foo.
The removal or (re)creation of foo changes what pages match it. Note that
this is true even if the pagespec currently fails to match.
+ >>> This is an annoying example (hence well worth having :) ). I think the
+ >>> indirect influence list must contain 'foo' and all currently matching
+ >>> pages. `created_before(foo)` will not match
+ >>> a deleted page, and so the base mechanism would not cause a rebuild. The
+ >>> removal problem strikes. -- [[Will]]
+
+ >>>> But `created_before` can in fact match a deleted page. Because the mtime
+ >>>> of a deleted page is temporarily set to 0 while the base mechanism runs to
+ >>>> find changes in deleted pages. (I verified this works by experiment,
+ >>>> also that `created_after` is triggered by a deleted page.) --[[Joey]]
+
+ >>>>> Oh, okie. I looked at the source, saw the `if (exists $IkiWiki::pagectime{$testpage})` and assumed it would fail.
+ >>>>> Of course, having it succeed doesn't cure all the issues -- just moves them. With `created_before()` succeeding
+ >>>>> for deleted files, this pagespec will be match any removal in the entire wiki with the base mechanism. Whether this is
+ >>>>> better or worse than the longer indirect influence list is an empirical question. -- [[Will]]
+
* The pagespec "foo" has an empty influence list. This is because a
modification/creation/removal of foo directly changes what the pagespec
matches.
>>>> pagespec, and see they used to match; and thus knows that the
>>>> dependency has triggered.
>>>>
+ >>>>> IkiWiki can only see that they used to match if they're in the glob matching set. -- [[Will]]
+ >>>>
>>>> Maybe the thing to do is consider this an optimisation, where such
>>>> pages are influences, but ikiwiki is able to implicitly find them,
>>>> so they do not need to be explicitly stored. --[[Joey]]
that contains index (because a change to index changes the backlinks).
Note that this is true even if the backlink currently fails.
+ >>> This is another interesting example. The missing document matching set contains all links on the page index, and so
+ >>> the influence list only needs to contain 'index' itself. -- [[Will]]
+
* The pagespec "link(done)" has an influence list that
contains every page that it matches. A change to any matching page can
remove a link and make it not match any more, and so the list is needed
`HardFailReason() | SuccessReason(bugs/foo)` =>
`HardFailReason()` => right
- #### High-level Calculation and Storage
-
- Naively calculating the full influence list for a pagespec requires trying
- to match it against every page in the wiki. I'd like to avoid doing such
- expensive matching redundantly.
-
- It may be possible, for some types of pagespecs, to just try matching a
- single, arbitrary page against it, and know the full influence list has
- been obtained. It seems to be that case that if a pagespec has any
- influences, matching any page will return at least one. So if none are
- returned, we can skip trying other pages.
-
- If the influence list does not include the page that was tried, we know
- that the pagespec does not things like `link()` and `title()`, that are
- influenced by the page's own content. So it *might* be safe to not try
- matching any more pages in this case too. I think it would work for all
- current pagespec terms. There might be a hypothetical term where this
- optimisation doesn't work. We could add a special case to ensure it can
- work: If a term declares it is unfluenced by "", then it means it is
- always influenced by the matching page.
-
- Anyway, this seems worth doing: Add a `pagespec_match_all`, which returns a
- list of all pages in the whole wiki that match the pagespec, and also adds
- the pagespec as a dependency, and while it's at it, calculates and stores
- the influence list.
-
- It could have an optional sort parameter, and limit parameter, to control
- how many items to return and the sort order. So when inline wants to
- display the 10 newest, only the influence lists for those ten are added.
-
- If `pagespec_match_depends` can be used by all plugins, then great,
- influences are automatically calculated, no extra work needs to be done.
-
- If not, and some plugins still need to use `pagespec_match_list` or
- `pagespec_match`, and `add_depends`, then I guess that `add_depends` can do
- a slightly more expensive influence calculation.
-
- Bonus: If `add_depends` is doing an influence calculation, then I can remove
- the nasty hack it currently uses to decide if a given pagespec is safe to use
- with an existence or links dependency.
-
- Where to store the influence list? Well, it appears that we can just add
- (content) dependencies for each item on the list, to the page's
- regular list of simple dependencies. So, the data stored ends up looking
- just like what is stored today by the explicit dependency hacks. Except,
- it's calculated more smartly, and is added automatically.
-
- > I've implemented influence calculation in `add_depends`. As expected,
- > it means rather a lot more work, and makes some things much slower.
- > Optimisations next.. --[[Joey]]
-
#### Influence types
Note that influences can also have types, same as dependency types.