001/*
002    Licensed to the Apache Software Foundation (ASF) under one
003    or more contributor license agreements.  See the NOTICE file
004    distributed with this work for additional information
005    regarding copyright ownership.  The ASF licenses this file
006    to you under the Apache License, Version 2.0 (the
007    "License"); you may not use this file except in compliance
008    with the License.  You may obtain a copy of the License at
009
010       http://www.apache.org/licenses/LICENSE-2.0
011
012    Unless required by applicable law or agreed to in writing,
013    software distributed under the License is distributed on an
014    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015    KIND, either express or implied.  See the License for the
016    specific language governing permissions and limitations
017    under the License.
018 */
019package org.apache.wiki.references;
020
021import org.apache.commons.lang3.time.StopWatch;
022import org.apache.logging.log4j.LogManager;
023import org.apache.logging.log4j.Logger;
024import org.apache.wiki.InternalWikiException;
025import org.apache.wiki.LinkCollector;
026import org.apache.wiki.api.core.Attachment;
027import org.apache.wiki.api.core.Context;
028import org.apache.wiki.api.core.Engine;
029import org.apache.wiki.api.core.Page;
030import org.apache.wiki.api.exceptions.ProviderException;
031import org.apache.wiki.api.filters.BasePageFilter;
032import org.apache.wiki.api.providers.PageProvider;
033import org.apache.wiki.api.providers.WikiProvider;
034import org.apache.wiki.api.spi.Wiki;
035import org.apache.wiki.attachment.AttachmentManager;
036import org.apache.wiki.event.WikiEvent;
037import org.apache.wiki.event.WikiEventManager;
038import org.apache.wiki.event.WikiPageEvent;
039import org.apache.wiki.pages.PageManager;
040import org.apache.wiki.parser.MarkupParser;
041import org.apache.wiki.parser.PluginContent;
042import org.apache.wiki.parser.WikiDocument;
043import org.apache.wiki.render.RenderingManager;
044import org.apache.wiki.util.Synchronizer;
045import org.apache.wiki.util.TextUtil;
046
047import org.jdom2.Content;
048import org.jdom2.filter.Filters;
049
050import java.io.*;
051import java.nio.charset.StandardCharsets;
052import java.nio.file.Files;
053import java.security.MessageDigest;
054import java.security.NoSuchAlgorithmException;
055import java.util.*;
056import java.util.concurrent.ConcurrentHashMap;
057import java.util.concurrent.atomic.AtomicLong;
058import java.util.concurrent.atomic.AtomicReference;
059import java.util.concurrent.locks.ReentrantLock;
060import java.util.stream.Collectors;
061
062/*
063  BUGS
064
065  - if a wikilink is added to a page, then removed, RefMan still thinks that the page refers to the wikilink page. Hm.
066
067  - if a page is deleted, gets very confused.
068
069  - Serialization causes page attributes to be missing, when InitializablePlugins are not executed properly.  Thus,
070    serialization should really also mark whether a page is serializable or not...
071 */
072
073
074/*
075   A word about synchronizing:
076
077   I expect this object to be accessed in three situations:
078   - when an Engine is created, and it scans its wikipages
079   - when the Engine saves a page
080   - when a JSP page accesses one of the Engine's ReferenceManagers to display a list of (un)referenced pages.
081
082   So, access to this class is fairly rare, and usually triggered by user interaction. OTOH, the methods in this class use their storage
083   objects intensively (and, sorry to say, in an unoptimized manner =). My deduction: using unsynchronized HashMaps etc. and syncing methods
084   or code blocks is preferrable to using slow, synced storage objects. We don't have iterative code here, so I'm going to use synced
085   methods for now.
086
087   Please contact me if you notice problems with ReferenceManager, and especially with synchronization, or if you have suggestions about
088   syncing.
089
090   ebu@memecry.net
091*/
092
093/**
094 *  Keeps track of wikipage references:
095 *  <UL>
096 *  <LI>What pages a given page refers to
097 *  <LI>What pages refer to a given page
098 *  </UL>
099 *
100 *  This is a quick'n'dirty approach without any finesse in storage and searching algorithms; we trust java.util.*.
101 *  <P>
102 *  This class contains two HashMaps, m_refersTo and m_referredBy. The first is indexed by WikiPage names and contains a Collection of all
103 *  WikiPages the page refers to. (Multiple references are not counted, naturally.) The second is indexed by WikiPage names and contains
104 *  a Set of all pages that refer to the indexing page. (Notice - the keys of both Maps should be kept in sync.)
105 *  <P>
106 *  When a page is added or edited, its references are parsed, a Collection is received, and we crudely replace anything previous with
107 *  this new Collection. We then check each referenced page name and make sure they know they are referred to by the new page.
108 *  <P>
109 *  Based on this information, we can perform non-optimal searches for e.g. unreferenced pages, top ten lists, etc.
110 *  <P>
111 *  The owning class must take responsibility of filling in any pre-existing information, probably by loading each and every WikiPage
112 *  and calling this class to update the references when created.
113 *
114 *  @since 1.6.1 (as of 2.11.0, moved to org.apache.wiki.references)
115 */
116
117// FIXME: The way that we save attributes is now a major booboo, and must be
118//        replaced forthwith.  However, this is a workaround for the great deal
119//        of problems that occur here...
120public class DefaultReferenceManager extends BasePageFilter implements ReferenceManager, Serializable {
121
122    /**
123     *  Maps page wikiname to a Collection of pages it refers to. The Collection must contain Strings. The Collection may contain
124     *  names of non-existing pages.
125     */
126    private Map< String, Collection< String > > m_refersTo;
127    private Map< String, Collection< String > > m_unmutableRefersTo;
128
129    /**
130     *  Maps page wikiname to a Set of referring pages. The Set must contain Strings. Non-existing pages (a reference exists, but
131     *  not a file for the page contents) may have an empty Set in m_referredBy.
132     */
133    private Map< String, Set< String > > m_referredBy;
134    private Map< String, Set< String > > m_unmutableReferredBy;
135
136    private final boolean m_matchEnglishPlurals;
137
138    private static final Logger LOG = LogManager.getLogger( DefaultReferenceManager.class);
139    private static final String INSERT_PAGE_PLUGIN = "InsertPage";
140    private static final String INSERT_PAGE_CLASS = "org.apache.wiki.plugin.InsertPage";
141    private static final String INSERT_PAGE_PARAMETER = "page";
142    private static final String SERIALIZATION_FILE = "refmgr.ser";
143    private static final String SERIALIZATION_DIR  = "refmgr-attr";
144
145    /** We use this also a generic serialization id */
146    private static final long serialVersionUID = 4L;
147
148    /**
149     * A lock used to ensure thread safety when accessing shared resources.
150     * This lock provides more flexibility and capabilities than the intrinsic locking mechanism,
151     * such as the ability to attempt to acquire a lock with a timeout, or to interrupt a thread
152     * waiting to acquire a lock.
153     *
154     * @see java.util.concurrent.locks.ReentrantLock
155     */
156    private final ReentrantLock lock = new ReentrantLock();
157
158    /**
159     *  Builds a new ReferenceManager.
160     *
161     *  @param engine The Engine to which this is managing references to.
162     */
163    public DefaultReferenceManager( final Engine engine ) {
164        m_refersTo = new ConcurrentHashMap<>();
165        m_referredBy = new ConcurrentHashMap<>();
166        m_engine = engine;
167        m_matchEnglishPlurals = TextUtil.getBooleanProperty( engine.getWikiProperties(), Engine.PROP_MATCHPLURALS, false );
168
169        //  Create two maps that contain unmutable versions of the two basic maps.
170        m_unmutableReferredBy = Collections.unmodifiableMap( m_referredBy );
171        m_unmutableRefersTo   = Collections.unmodifiableMap( m_refersTo );
172    }
173
174    /**
175     *  Does a full reference update.  Does not sync; assumes that you do it afterwards.
176     */
177    private void updatePageReferences( final Page page ) throws ProviderException {
178        final String content = m_engine.getManager( PageManager.class ).getPageText( page.getName(), PageProvider.LATEST_VERSION );
179        final Collection< String > links = scanWikiLinks( page, content );
180        final TreeSet< String > res = new TreeSet<>( links );
181        final List< Attachment > attachments = m_engine.getManager( AttachmentManager.class ).listAttachments( page );
182        for( final Attachment att : attachments ) {
183            res.add( att.getName() );
184        }
185
186        internalUpdateReferences( page.getName(), res );
187    }
188
189    /**
190     *  Initializes the entire reference manager with the initial set of pages from the collection.
191     *
192     *  @param pages A collection of all pages you want to be included in the reference count.
193     *  @since 2.2
194     *  @throws ProviderException If reading of pages fails.
195     */
196    @Override
197    public void initialize( final Collection< Page > pages ) throws ProviderException {
198        LOG.debug( "Initializing new ReferenceManager with {} initial pages.", pages.size() );
199        final StopWatch sw = new StopWatch();
200        sw.start();
201        LOG.info( "Starting cross reference scan of WikiPages" );
202
203        //  First, try to serialize old data from disk.  If that fails, we'll go and update the entire reference lists (which'll take time)
204        try {
205            //  Unserialize things.  The loop below cannot be combined with the other loop below, simply because
206            //  engine.getPage() has side effects such as loading initializing the user databases, which in turn want all
207            //  the pages to be read already...
208            //
209            //  Yes, this is a kludge.  We know.  Will be fixed.
210            final long saved = unserializeFromDisk();
211
212            for( final Page page : pages ) {
213                unserializeAttrsFromDisk( page );
214            }
215
216            //  Now we must check if any of the pages have been changed  while we were in the electronic la-la-land,
217            //  and update the references for them.
218            for( final Page page : pages ) {
219                if( !( page instanceof Attachment ) ) {
220                    // Refresh with the latest copy
221                    final Page wp = m_engine.getManager( PageManager.class ).getPage( page.getName() );
222
223                    if( wp.getLastModified() == null ) {
224                        LOG.fatal( "Provider returns null lastModified.  Please submit a bug report." );
225                    } else if( wp.getLastModified().getTime() > saved ) {
226                        updatePageReferences( wp );
227                    }
228                }
229            }
230
231        } catch( final Exception e ) {
232            LOG.info( "Unable to unserialize old refmgr information, rebuilding database: {}", e.getMessage() );
233            buildKeyLists( pages );
234
235            // Scan the existing pages from disk and update references in the manager.
236            for( final Page page : pages ) {
237                // We cannot build a reference list from the contents of attachments, so we skip them.
238                if( !( page instanceof Attachment ) ) {
239                    updatePageReferences( page );
240                    serializeAttrsToDisk( page );
241                }
242            }
243
244            serializeToDisk();
245        }
246
247        sw.stop();
248        LOG.info( "Cross reference scan done in {}", sw );
249
250        WikiEventManager.addWikiEventListener( m_engine.getManager( PageManager.class ), this );
251    }
252
253    /**
254     *  Reads the serialized data from the disk back to memory. Returns the date when the data was last written on disk
255     */
256    @SuppressWarnings("unchecked")
257    private long unserializeFromDisk() throws IOException, ClassNotFoundException {
258        final AtomicLong saved = new AtomicLong(0);
259        Synchronizer.synchronize(lock, () -> {
260            try {
261                final File f = new File(m_engine.getWorkDir(), SERIALIZATION_FILE);
262                try (final ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(Files.newInputStream(f.toPath())))) {
263                    final StopWatch sw = new StopWatch();
264                    sw.start();
265
266                    final long ver = in.readLong();
267
268                    if (ver != serialVersionUID) {
269                        throw new IOException("File format has changed; I need to recalculate references.");
270                    }
271
272                    saved.set(in.readLong());
273                    m_refersTo = (Map<String, Collection<String>>) in.readObject();
274                    m_referredBy = (Map<String, Set<String>>) in.readObject();
275
276                    m_unmutableReferredBy = Collections.unmodifiableMap(m_referredBy);
277                    m_unmutableRefersTo = Collections.unmodifiableMap(m_refersTo);
278
279                    sw.stop();
280                    LOG.debug("Read serialized data successfully in {}", sw);
281                }
282            } catch (IOException | ClassNotFoundException e) {
283                throw new RuntimeException(e);
284            }
285        });
286
287        return saved.get();
288    }
289
290
291    /**
292     *  Serializes hashmaps to disk.  The format is private, don't touch it.
293     */
294    private void serializeToDisk() {
295        Synchronizer.synchronize(lock, () -> {
296            final File f = new File(m_engine.getWorkDir(), SERIALIZATION_FILE);
297            try (final ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(Files.newOutputStream(f.toPath())))) {
298                final StopWatch sw = new StopWatch();
299                sw.start();
300
301                out.writeLong(serialVersionUID);
302                out.writeLong(System.currentTimeMillis()); // Timestamp
303                out.writeObject(m_refersTo);
304                out.writeObject(m_referredBy);
305
306                sw.stop();
307
308                LOG.debug("serialization done - took {}", sw);
309            } catch (final IOException ioe) {
310                LOG.error("Unable to serialize!", ioe);
311            }
312        });
313    }
314
315    private String getHashFileName( final String pageName ) {
316        if( pageName == null ) {
317            return null;
318        }
319        try {
320            final MessageDigest digest = MessageDigest.getInstance( "MD5" );
321            final byte[] dig = digest.digest( pageName.getBytes( StandardCharsets.UTF_8 ) );
322
323            return TextUtil.toHexString( dig ) + ".cache";
324        } catch( final NoSuchAlgorithmException e ) {
325            LOG.fatal( "What do you mean - no such algorithm?", e );
326            return null;
327        }
328    }
329
330    /**
331     *  Reads the serialized data from the disk back to memory. Returns the date when the data was last written on disk
332     */
333    private long unserializeAttrsFromDisk(final Page p) throws IOException, ClassNotFoundException {
334        final AtomicLong saved = new AtomicLong(0L);
335        final AtomicReference<IOException> ioExceptionRef = new AtomicReference<>();
336        final AtomicReference<ClassNotFoundException> classNotFoundExceptionRef = new AtomicReference<>();
337
338        Synchronizer.synchronize(lock, () -> {
339            try {
340                long localSaved = 0L;
341
342                // Find attribute cache, and check if it exists
343                final String hashName = getHashFileName(p.getName());
344                if (hashName != null) {
345                    File f = new File(m_engine.getWorkDir(), SERIALIZATION_DIR);
346                    f = new File(f, hashName);
347                    if (!f.exists()) {
348                        return;
349                    }
350
351                    try (final ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(Files.newInputStream(f.toPath())))) {
352                        // ... existing code here
353                        final long ver = in.readLong();
354                        if (ver != serialVersionUID) {
355                            // Log or handle as needed
356                            return;
357                        }
358
359                        localSaved = in.readLong();
360                        final String name = in.readUTF();
361                        if (!name.equals(p.getName())) {
362                            // Log or handle as needed
363                            return;
364                        }
365
366                        final long entries = in.readLong();
367                        for (int i = 0; i < entries; i++) {
368                            final String key = in.readUTF();
369                            final Object value = in.readObject();
370                            p.setAttribute(key, value);
371                            // Log or handle as needed
372                        }
373                    }
374                }
375
376                saved.set(localSaved);
377            } catch (IOException e) {
378                ioExceptionRef.set(e);
379            } catch (ClassNotFoundException e) {
380                classNotFoundExceptionRef.set(e);
381            }
382        });
383
384        if (ioExceptionRef.get() != null) {
385            throw ioExceptionRef.get();
386        }
387
388        if (classNotFoundExceptionRef.get() != null) {
389            throw classNotFoundExceptionRef.get();
390        }
391
392        return saved.get();
393    }
394
395    /**
396     *  Serializes hashmaps to disk.  The format is private, don't touch it.
397     */
398    private void serializeAttrsToDisk( final Page p ) {
399        Synchronizer.synchronize(lock, () -> {
400            final StopWatch sw = new StopWatch();
401            sw.start();
402
403            final String hashName = getHashFileName( p.getName() );
404            if( hashName != null ) {
405                File f = new File( m_engine.getWorkDir(), SERIALIZATION_DIR );
406                if( !f.exists() ) {
407                    f.mkdirs();
408                }
409
410                //  Create a digest for the name
411                f = new File( f, hashName );
412
413                try( final ObjectOutputStream out =  new ObjectOutputStream( new BufferedOutputStream( Files.newOutputStream( f.toPath() ) ) ) ) {
414                    // new Set to avoid concurrency issues
415                    final Set< Map.Entry < String, Object > > entries = new HashSet<>( p.getAttributes().entrySet() );
416
417                    if(entries.isEmpty()) {
418                        //  Nothing to serialize, therefore we will just simply remove the serialization file so that the
419                        //  next time we boot, we don't deserialize old data.
420                        f.delete();
421                        return;
422                    }
423
424                    out.writeLong( serialVersionUID );
425                    out.writeLong( System.currentTimeMillis() ); // Timestamp
426                    out.writeUTF( p.getName() );
427                    out.writeLong( entries.size() );
428
429                    for( final Map.Entry< String, Object > e : entries ) {
430                        if( e.getValue() instanceof Serializable ) {
431                            out.writeUTF( e.getKey() );
432                            out.writeObject( e.getValue() );
433                        }
434                    }
435
436                } catch( final IOException e ) {
437                    LOG.error( "Unable to serialize!", e );
438                } finally {
439                    sw.stop();
440                    LOG.debug( "serialization for {} done - took {}", p.getName(), sw );
441                }
442            }
443        });
444    }
445
446    /**
447     *  After the page has been saved, updates the reference lists.
448     *
449     *  @param context {@inheritDoc}
450     *  @param content {@inheritDoc}
451     */
452    @Override
453    public void postSave( final Context context, final String content ) {
454        final Page page = context.getPage();
455        updateReferences( page.getName(), scanWikiLinks( page, content ) );
456        serializeAttrsToDisk( page );
457    }
458
459    /**
460     *  Reads a WikiPageful of data from a String and returns all links internal to this Wiki in a Collection.
461     *
462     *  @param page The WikiPage to scan
463     *  @param pagedata The page contents
464     *  @return a Collection of Strings
465     */
466    @Override
467    public Collection< String > scanWikiLinks( final Page page, final String pagedata ) {
468        final LinkCollector localCollector = new LinkCollector();
469        m_engine.getManager( RenderingManager.class ).textToHTML( Wiki.context().create( m_engine, page ),
470                                                                  pagedata,
471                                                                  localCollector,
472                                                                  null,
473                                                                  localCollector,
474                                                                  false,
475                                                                  true );
476
477        final List< String > links = localCollector.getLinks();
478        if( pagedata != null && pagedata.contains( INSERT_PAGE_PLUGIN ) ) {
479            links.addAll( insertedPages( page, pagedata ) );
480        }
481
482        return links;
483    }
484
485    /**
486     *  The parser reports the links of a text but not the pages that a plugin names, so the pages that the plugin InsertPage
487     *  includes are found in the parsed text: a page that is inserted in another one is referenced by it, as if it were linked.
488     */
489    private List< String > insertedPages( final Page page, final String pagedata ) {
490        final List< String > pages = new ArrayList<>();
491        try {
492            final WikiDocument document = m_engine.getManager( RenderingManager.class )
493                                                  .getParser( Wiki.context().create( m_engine, page ), pagedata )
494                                                  .parse();
495            for( final Content content : document.getDescendants( Filters.content() ) ) {
496                if( content instanceof PluginContent ) {
497                    final PluginContent plugin = ( PluginContent ) content;
498                    final String name = plugin.getPluginName();
499                    final String inserted = plugin.getParameter( INSERT_PAGE_PARAMETER );
500                    if( inserted != null && ( INSERT_PAGE_PLUGIN.equals( name ) || INSERT_PAGE_CLASS.equals( name ) ) ) {
501                        pages.add( MarkupParser.cleanLink( inserted ) );
502                    }
503                }
504            }
505        } catch( final IOException e ) {
506            LOG.warn( "Could not look for the pages inserted in {}: {}", page.getName(), e.getMessage() );
507        }
508
509        return pages;
510    }
511
512    /**
513     * Updates the m_referedTo and m_referredBy hashmaps when a page has been deleted.
514     * <P>
515     * Within the m_refersTo map the pagename is a key. The whole key-value-set has to be removed to keep the map clean.
516     * Within the m_referredBy map the name is stored as a value. Since a key can have more than one value we have to
517     * delete just the key-value-pair referring page:deleted page.
518     *
519     *  @param page Name of the page to remove from the maps.
520     */
521    @Override
522    public void pageRemoved( final Page page ) {
523        pageRemoved( page.getName() );
524    }
525
526    private void pageRemoved( final String pageName ) {
527        final Collection< String > refTo = m_refersTo.get( pageName );
528        if( refTo != null ) {
529            for( final String referredPageName : refTo ) {
530                final Set< String > refBy = m_referredBy.get( referredPageName );
531                if( refBy == null ) {
532                    throw new InternalWikiException( "Refmgr out of sync: page " + pageName +
533                                                     " refers to " + referredPageName + ", which has null referrers." );
534                }
535
536                refBy.remove( pageName );
537                m_referredBy.remove( referredPageName );
538
539                // We won't put it back again if it becomes empty and does not exist.  It will be added
540                // later on anyway, if it becomes referenced again.
541                if( !( refBy.isEmpty() && !m_engine.getManager( PageManager.class ).wikiPageExists( referredPageName ) ) ) {
542                    m_referredBy.put( referredPageName, refBy );
543                }
544            }
545
546            LOG.debug( "Removing from m_refersTo HashMap key:value {}:{}", pageName, m_refersTo.get( pageName ) );
547            m_refersTo.remove( pageName );
548        }
549
550        final Set< String > refBy = m_referredBy.get( pageName );
551        if( refBy == null || refBy.isEmpty() ) {
552            m_referredBy.remove( pageName );
553        }
554
555        //  Remove any traces from the disk, too
556        serializeToDisk();
557
558        final String hashName = getHashFileName( pageName );
559        if( hashName != null ) {
560            File f = new File( m_engine.getWorkDir(), SERIALIZATION_DIR );
561            f = new File( f, getHashFileName( pageName ) );
562            if( f.exists() ) {
563                f.delete();
564            }
565        }
566    }
567
568    /**
569     *  Updates all references for the given page.
570     *
571     *  @param page wiki page for which references should be updated
572     */
573    @Override
574    public void updateReferences( final Page page ) {
575        final String pageData = m_engine.getManager( PageManager.class ).getPureText( page.getName(), WikiProvider.LATEST_VERSION );
576        updateReferences( page.getName(), scanWikiLinks( page, pageData ) );
577    }
578
579    /**
580     *  Updates the referred pages of a new or edited WikiPage. If a refersTo entry for this page already exists, it is removed
581     *  and a new one is built from scratch. Also calls updateReferredBy() for each referenced page.
582     *  <P>
583     *  This is the method to call when a new page has been created, and we want to a) set up its references and b) notify the
584     *  referred pages of the references. Use this method during run-time.
585     *
586     *  @param page Name of the page to update.
587     *  @param references A Collection of Strings, each one pointing to a page this page references.
588     */
589    @Override
590    public void updateReferences( final String page, final Collection< String > references ) {
591        internalUpdateReferences( page, references );
592        serializeToDisk();
593    }
594
595    /**
596     *  Updates the referred pages of a new or edited WikiPage. If a refersTo entry for this page already exists, it is
597     *  removed and a new one is built from scratch. Also calls updateReferredBy() for each referenced page.
598     *  <p>
599     *  This method does not synchronize the database to disk.
600     *
601     *  @param page Name of the page to update.
602     *  @param references A Collection of Strings, each one pointing to a page this page references.
603     */
604    private void internalUpdateReferences( String page, final Collection< String > references) {
605        page = getFinalPageName( page );
606
607        // Create a new entry in m_refersTo.
608        final Collection< String > oldRefTo = m_refersTo.get( page );
609        m_refersTo.remove( page );
610
611        final TreeSet< String > cleanedRefs = references.stream().map(this::getFinalPageName).collect(Collectors.toCollection(TreeSet::new));
612
613        m_refersTo.put( page, cleanedRefs );
614
615        //  We know the page exists, since it's making references somewhere. If an entry for it didn't exist previously
616        //  in m_referredBy, make sure one is added now.
617        if( !m_referredBy.containsKey( page ) ) {
618            m_referredBy.put( page, new TreeSet<>() );
619        }
620
621        //  Get all pages that used to be referred to by 'page' and remove that reference. (We don't want to try to figure out
622        //  which particular references were removed...)
623        cleanReferredBy( page, oldRefTo);
624
625        //  Notify all referred pages of their referinesshoodicity.
626        for( final String referredPageName : cleanedRefs ) {
627            updateReferredBy( getFinalPageName( referredPageName ), page );
628        }
629    }
630
631    /**
632     * Returns the refers-to list. For debugging.
633     *
634     * @return The refers-to list.
635     */
636    protected Map< String, Collection< String > > getRefersTo() {
637        return m_refersTo;
638    }
639
640    /**
641     * Returns the referred-by list. For debugging.
642     *
643     * @return Referred-by lists.
644     */
645    protected Map< String, Set< String > > getReferredBy() {
646        return m_referredBy;
647    }
648
649    /**
650     * Cleans the 'referred by' list, removing references by 'referrer' to any other page. Called after 'referrer' is removed.
651     * Two ways to go about this. One is to look up all pages previously referred by referrer and remove referrer
652     * from their lists, and let the update put them back in (except possibly removed ones).
653     * The other is to get the old referred-to list, compare to the new, and tell the ones missing in the latter to remove referrer from
654     * their list.
655     * We'll just try the first for now. Need to come back and optimize this a bit.
656     */
657    private void cleanReferredBy( final String referrer,
658                                  final Collection< String > oldReferred ) {
659        if( oldReferred == null ) {
660            return;
661        }
662
663        for( final String referredPage : oldReferred ) {
664            final Set< String > oldRefBy = m_referredBy.get( referredPage );
665            if( oldRefBy != null ) {
666                oldRefBy.remove( referrer );
667            }
668
669            // If the page is referred to by no one AND it doesn't even exist, we might just as well forget about this
670            // entry. It will be added again elsewhere if new references appear.
671            if( ( oldRefBy == null || oldRefBy.isEmpty() ) && !m_engine.getManager( PageManager.class ).wikiPageExists( referredPage ) ) {
672                m_referredBy.remove( referredPage );
673            }
674        }
675    }
676
677    /**
678     * When initially building a ReferenceManager from scratch, call this method BEFORE calling updateReferences() with
679     * a full list of existing page names. It builds the refersTo and referredBy key lists, thus enabling updateReferences()
680     * to function correctly.
681     * <P>
682     * This method should NEVER be called after initialization. It clears all mappings from the reference tables.
683     *
684     * @param pages a Collection containing WikiPage objects.
685     */
686    private void buildKeyLists( final Collection< Page > pages ) {
687        m_refersTo.clear();
688        m_referredBy.clear();
689        if( pages == null ) {
690            return;
691        }
692
693        try {
694            for( final Page page : pages ) {
695                // We add a non-null entry to referredBy to indicate the referred page exists
696                m_referredBy.put( page.getName(), new TreeSet<>() );
697                // Just add a key to refersTo; the keys need to be in sync with referredBy.
698                m_refersTo.put( page.getName(), new TreeSet<>() );
699            }
700        } catch( final ClassCastException e ) {
701            LOG.fatal( "Invalid collection entry in ReferenceManager.buildKeyLists().", e );
702        }
703    }
704
705
706    /**
707     * Marks the page as referred to by the referrer. If the page does not exist previously, nothing is done. (This means
708     * that some page, somewhere, has a link to a page that does not exist.)
709     */
710    private void updateReferredBy( final String page, final String referrer ) {
711        // We're not really interested in first level self-references.
712        /*
713        if( page.equals( referrer ) )
714        {
715            return;
716        }
717        */
718        // Neither are we interested if plural forms refer to each other.
719        if( m_matchEnglishPlurals ) {
720            final String p2 = page.endsWith( "s" ) ? page.substring( 0, page.length() - 1 ) : page + "s";
721            if( referrer.equals( p2 ) ) {
722                return;
723            }
724        }
725
726        // Even if 'page' has not been created yet, it can still be referenced. This requires we don't use m_referredBy
727        // keys when looking up missing pages, of course.
728        final Set< String > referrers = m_referredBy.computeIfAbsent( page, k -> new TreeSet<>() );
729        referrers.add( referrer );
730    }
731
732
733    /**
734     * Clears the references to a certain page, so it's no longer in the map.
735     *
736     * @param pagename  Name of the page to clear references for.
737     */
738    @Override
739    public void clearPageEntries( String pagename ) {
740        pagename = getFinalPageName( pagename );
741
742        //  Remove this item from the referredBy list of any page which this item refers to.
743        final Collection< String > c = m_refersTo.get( pagename );
744        if( c != null ) {
745            for( final String key : c ) {
746                final Collection< ? > dref = m_referredBy.get( key );
747                dref.remove( pagename );
748            }
749        }
750
751        //  Finally, remove direct references.
752        m_referredBy.remove( pagename );
753        m_refersTo.remove( pagename );
754    }
755
756
757    /**
758     *  Finds all unreferenced pages. This requires a linear scan through m_referredBy to locate keys with null or empty values.
759     *
760     *  @return The Collection of Strings
761     */
762    @Override
763    public Collection< String > findUnreferenced() {
764        final ArrayList< String > unref = new ArrayList<>();
765        for( final String key : m_referredBy.keySet() ) {
766            final Set< ? > refs = getReferenceList( m_referredBy, key );
767            if( refs == null || refs.isEmpty() ) {
768                unref.add( key );
769            }
770        }
771
772        return unref;
773    }
774
775
776    /**
777     * Finds all references to non-existant pages. This requires a linear scan through m_refersTo values; each value
778     * must have a corresponding key entry in the reference Maps, otherwise such a page has never been created.
779     * <P>
780     * Returns a Collection containing Strings of unreferenced page names. Each non-existant page name is shown only
781     * once - we don't return information on who referred to it.
782     *
783     * @return A Collection of Strings
784     */
785    @Override
786    public Collection< String > findUncreated() {
787        final TreeSet< String > uncreated;
788
789        // Go through m_refersTo values and check that m_refersTo has the corresponding keys.
790        // We want to reread the code to make sure our HashMaps are in sync...
791        final Collection< Collection< String > > allReferences = m_refersTo.values();
792        uncreated = allReferences.stream().filter(Objects::nonNull).flatMap(Collection::stream).filter(aReference -> !m_engine.getManager(PageManager.class).wikiPageExists(aReference)).collect(Collectors.toCollection(TreeSet::new));
793
794        return uncreated;
795    }
796
797    /**
798     *  Searches for the given page in the given Map, and returns the set of references. This method also takes care of
799     *  English plural matching.
800     *
801     *  @param coll The Map to search in
802     *  @param pagename The name to find.
803     *  @return The references list.
804     */
805    private < T > Set< T > getReferenceList( final Map< String, Set< T > > coll, final String pagename ) {
806        Set< T > refs = coll.get( pagename );
807
808        if( m_matchEnglishPlurals ) {
809            //  We'll add also matches from the "other" page.
810            final Set< T > refs2;
811
812            if( pagename.endsWith( "s" ) ) {
813                refs2 = coll.get( pagename.substring( 0, pagename.length() - 1 ) );
814            } else {
815                refs2 = coll.get( pagename + "s" );
816            }
817
818            if( refs2 != null ) {
819                if( refs != null ) {
820                    refs.addAll( refs2 );
821                } else {
822                    refs = refs2;
823                }
824            }
825        }
826        return refs;
827    }
828
829    /**
830     * Find all pages that refer to this page. Returns null if the page does not exist or is not referenced at all,
831     * otherwise returns a collection containing page names (String) that refer to this one.
832     * <p>
833     * @param pagename The page to find referrers for.
834     * @return A Set of Strings.  May return null, if the page does not exist, or if it has no references.
835     */
836    @Override
837    public Set< String > findReferrers( final String pagename ) {
838        final Set< String > refs = getReferenceList( m_referredBy, pagename );
839        if( refs == null || refs.isEmpty() ) {
840            return null;
841        }
842
843        return refs;
844    }
845
846    /**
847     *  Returns all pages that refer to this page.  Note that this method returns an unmodifiable Map, which may be abruptly changed.
848     *  So any access to any iterator may result in a ConcurrentModificationException.
849     *  <p>
850     *  The advantages of using this method over findReferrers() is that it is very fast, as it does not create a new object.
851     *  The disadvantages are that it does not do any mapping between plural names, and you may end up getting a
852     *  ConcurrentModificationException.
853     *
854     * @param pageName Page name to query.
855     * @return A Set of Strings containing the names of all the pages that refer to this page.  May return null, if the page does
856     *         not exist or has not been indexed yet.
857     * @since 2.2.33
858     */
859    @Override
860    public Set< String > findReferredBy( final String pageName ) {
861        return m_unmutableReferredBy.get( getFinalPageName(pageName) );
862    }
863
864    /**
865     *  Returns all pages that this page refers to.  You can use this as a quick way of getting the links from a page, but note
866     *  that it does not link any InterWiki, image, or external links.  It does contain attachments, though.
867     *  <p>
868     *  The Collection returned is unmutable, so you cannot change it.  It does reflect the current status and thus is a live
869     *  object.  So, if you are using any kind of an iterator on it, be prepared for ConcurrentModificationExceptions.
870     *  <p>
871     *  The returned value is a Collection, because a page may refer to another page multiple times.
872     *
873     * @param pageName Page name to query
874     * @return A Collection of Strings containing the names of the pages that this page refers to. May return null, if the page
875     *         does not exist or has not been indexed yet.
876     * @since 2.2.33
877     */
878    @Override
879    public Collection< String > findRefersTo( final String pageName ) {
880        return m_unmutableRefersTo.get( getFinalPageName( pageName ) );
881    }
882
883    /**
884     * This 'deepHashCode' can be used to determine if there were any modifications made to the underlying to and by maps of the
885     * ReferenceManager. The maps of the ReferenceManager are not synchronized, so someone could add/remove entries in them while the
886     * hashCode is being computed.
887     * This method traps and retries if a concurrent modification occurs.
888     *
889     * @return Sum of the hashCodes for the 'to' and 'by' maps of the ReferenceManager
890     * @since 2.3.24
891     */
892    //
893    //   TODO: It is unnecessary to calculate the hashcode; it should be calculated only when the hashmaps are changed.  This is slow.
894    //
895    public int deepHashCode() {
896        boolean failed = true;
897        int signature = 0;
898
899        while( failed ) {
900            signature = 0;
901            try {
902                signature ^= m_referredBy.hashCode();
903                signature ^= m_refersTo.hashCode();
904                failed = false;
905            } catch ( final ConcurrentModificationException e) {
906                Thread.yield();
907            }
908        }
909
910        return signature;
911    }
912
913    /**
914     *  Returns a list of all pages that the ReferenceManager knows about. This should be roughly equivalent to
915     *  PageManager.getAllPages(), but without the potential disk access overhead.  Note that this method is not guaranteed
916     *  to return a Set of really all pages (especially during startup), but it is very fast.
917     *
918     *  @return A Set of all defined page names that ReferenceManager knows about.
919     *  @since 2.3.24
920     */
921    @Override
922    public Set< String > findCreated() {
923        return new HashSet<>( m_refersTo.keySet() );
924    }
925
926    private String getFinalPageName( final String orig ) {
927        try {
928            final String s = m_engine.getFinalPageName( orig );
929            return s != null ? s : orig;
930        } catch( final ProviderException e ) {
931            LOG.error( "Error while trying to fetch a page name; trying to cope with the situation.", e );
932            return orig;
933        }
934    }
935
936    /**
937     *  {@inheritDoc}
938     */
939    @Override
940    public void actionPerformed( final WikiEvent event ) {
941        if( event instanceof WikiPageEvent && event.getType() == WikiPageEvent.PAGE_DELETED ) {
942            final String pageName = ( ( WikiPageEvent ) event ).getPageName();
943            if( pageName != null ) {
944                pageRemoved( pageName );
945            }
946        }
947    }
948
949}