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*/
019
020package org.apache.wiki.diff;
021
022import org.apache.logging.log4j.LogManager;
023import org.apache.logging.log4j.Logger;
024import org.apache.wiki.api.core.Context;
025import org.apache.wiki.api.core.Engine;
026import org.apache.wiki.api.exceptions.NoRequiredPropertyException;
027import org.apache.wiki.util.TextUtil;
028import org.suigeneris.jrcs.diff.Diff;
029import org.suigeneris.jrcs.diff.DifferentiationFailedException;
030import org.suigeneris.jrcs.diff.Revision;
031import org.suigeneris.jrcs.diff.RevisionVisitor;
032import org.suigeneris.jrcs.diff.delta.AddDelta;
033import org.suigeneris.jrcs.diff.delta.ChangeDelta;
034import org.suigeneris.jrcs.diff.delta.Chunk;
035import org.suigeneris.jrcs.diff.delta.DeleteDelta;
036import org.suigeneris.jrcs.diff.delta.Delta;
037import org.suigeneris.jrcs.diff.myers.MyersDiff;
038
039import java.io.IOException;
040import java.util.ArrayList;
041import java.util.List;
042import java.util.Properties;
043import java.util.StringTokenizer;
044
045
046/**
047 * A seriously better diff provider, which highlights changes word-by-word using CSS.
048 *
049 * Suggested by John Volkar.
050 */
051public class ContextualDiffProvider implements DiffProvider {
052
053    private static final Logger log = LogManager.getLogger( ContextualDiffProvider.class );
054
055    /**
056     *  A jspwiki.properties value to define how many characters are shown around the change context.
057     *  The current value is <tt>{@value}</tt>.
058     */
059    public static final String PROP_UNCHANGED_CONTEXT_LIMIT = "jspwiki.contextualDiffProvider.unchangedContextLimit";
060
061    //TODO all of these publics can become jspwiki.properties entries...
062    //TODO span title= can be used to get hover info...
063
064    public boolean m_emitChangeNextPreviousHyperlinks = true;
065
066    //Don't use spans here the deletion and insertions are nested in this...
067    public static String CHANGE_START_HTML = ""; //This could be a image '>' for a start marker
068    public static String CHANGE_END_HTML = ""; //and an image for an end '<' marker
069    public static String DIFF_START = "<div class=\"diff-wikitext\">";
070    public static String DIFF_END = "</div>";
071
072    // Unfortunately we need to do dumb HTML here for RSS feeds.
073
074    public static String INSERTION_START_HTML = "<font color=\"#8000FF\"><span class=\"diff-insertion\">";
075    public static String INSERTION_END_HTML = "</span></font>";
076    public static String DELETION_START_HTML = "<strike><font color=\"red\"><span class=\"diff-deletion\">";
077    public static String DELETION_END_HTML = "</span></font></strike>";
078    private static final String ANCHOR_PRE_INDEX = "<a name=\"change-";
079    private static final String ANCHOR_POST_INDEX = "\" />";
080    private static final String BACK_PRE_INDEX = "<a class=\"diff-nextprev\" title=\"Go to previous change\" href=\"#change-";
081    private static final String BACK_POST_INDEX = "\">&lt;&lt;</a>";
082    private static final String FORWARD_PRE_INDEX = "<a class=\"diff-nextprev\" title=\"Go to next change\" href=\"#change-";
083    private static final String FORWARD_POST_INDEX = "\">&gt;&gt;</a>";
084    public static String ELIDED_HEAD_INDICATOR_HTML = "<br/><br/><b>...</b>";
085    public static String ELIDED_TAIL_INDICATOR_HTML = "<b>...</b><br/><br/>";
086    public static String LINE_BREAK_HTML = "<br />";
087    public static String ALTERNATING_SPACE_HTML = "&nbsp;";
088
089    // This one, I will make property file based...
090    private static final int LIMIT_MAX_VALUE = (Integer.MAX_VALUE /2) - 1;
091    private int m_unchangedContextLimit = LIMIT_MAX_VALUE;
092
093
094    /**
095     *  Constructs this provider.
096     */
097    public ContextualDiffProvider()
098    {}
099
100    /**
101     * @see org.apache.wiki.api.providers.WikiProvider#getProviderInfo()
102     * 
103     * {@inheritDoc}
104     */
105    @Override
106    public String getProviderInfo()
107    {
108        return "ContextualDiffProvider";
109    }
110
111    /**
112     * @see org.apache.wiki.api.providers.WikiProvider#initialize(org.apache.wiki.api.core.Engine, java.util.Properties)
113     *      
114     * {@inheritDoc}
115     */
116    @Override
117    public void initialize( final Engine engine, final Properties properties) throws NoRequiredPropertyException, IOException {
118        final String configuredLimit = properties.getProperty( PROP_UNCHANGED_CONTEXT_LIMIT, Integer.toString( LIMIT_MAX_VALUE ) );
119        int limit = LIMIT_MAX_VALUE;
120        try {
121            limit = Integer.parseInt( configuredLimit );
122        } catch( final NumberFormatException e ) {
123            log.warn("Failed to parseInt " + PROP_UNCHANGED_CONTEXT_LIMIT + "=" + configuredLimit + " Will use a huge number as limit.", e );
124        }
125        m_unchangedContextLimit = limit;
126    }
127
128
129
130    /**
131     * Do a colored diff of the two regions. This. is. serious. fun. ;-)
132     *
133     * @see org.apache.wiki.diff.DiffProvider#makeDiffHtml(Context, String, String)
134     * 
135     * {@inheritDoc}
136     */
137    @Override
138    public synchronized String makeDiffHtml( final Context ctx, final String wikiOld, final String wikiNew ) {
139        //
140        // Sequencing handles lineterminator to <br /> and every-other consequtive space to a &nbsp;
141        //
142        final String[] alpha = sequence( TextUtil.replaceEntities( wikiOld ) );
143        final String[] beta  = sequence( TextUtil.replaceEntities( wikiNew ) );
144
145        final Revision rev;
146        try {
147            rev = Diff.diff( alpha, beta, new MyersDiff() );
148        } catch( final DifferentiationFailedException dfe ) {
149            log.error( "Diff generation failed", dfe );
150            return "Error while creating version diff.";
151        }
152
153        final int revSize = rev.size();
154        final StringBuffer sb = new StringBuffer();
155
156        sb.append( DIFF_START );
157
158        //
159        // The MyersDiff is a bit dumb by converting a single line multi-word diff into a series
160        // of Changes. The ChangeMerger pulls them together again...
161        //
162        final ChangeMerger cm = new ChangeMerger( sb, alpha, revSize );
163        rev.accept( cm );
164        cm.shutdown();
165        sb.append( DIFF_END );
166        return sb.toString();
167    }
168
169    /**
170     * Take the string and create an array from it, split it first on newlines, making
171     * sure to preserve the newlines in the elements, split each resulting element on
172     * spaces, preserving the spaces.
173     *
174     * All this preseving of newlines and spaces is so the wikitext when diffed will have fidelity
175     * to it's original form.  As a side affect we see edits of purely whilespace.
176     */
177    private String[] sequence( final String wikiText ) {
178        final String[] linesArray = Diff.stringToArray( wikiText );
179        final List< String > list = new ArrayList<>();
180        for( final String line : linesArray ) {
181
182            String lastToken = null;
183            String token;
184            // StringTokenizer might be discouraged but it still is perfect here...
185            for( final StringTokenizer st = new StringTokenizer( line, " ", true ); st.hasMoreTokens(); ) {
186                token = st.nextToken();
187
188                if( " ".equals( lastToken ) && " ".equals( token ) ) {
189                    token = ALTERNATING_SPACE_HTML;
190                }
191
192                list.add( token );
193                lastToken = token;
194            }
195
196            list.add( LINE_BREAK_HTML ); // Line Break
197        }
198
199        return list.toArray( new String[ 0 ] );
200    }
201
202    /**
203     * This helper class does the housekeeping for merging
204     * our various changes down and also makes sure that the
205     * whole change process is threadsafe by encapsulating
206     * all necessary variables.
207     */
208    private final class ChangeMerger implements RevisionVisitor {
209        private final StringBuffer m_sb;
210
211        /** Keeping score of the original lines to process */
212        private final int m_max;
213
214        private int m_index;
215
216        /** Index of the next element to be copied into the output. */
217        private int m_firstElem;
218
219        /** Link Anchor counter */
220        private int m_count = 1;
221
222        /** State Machine Mode */
223        private int m_mode = -1; /* -1: Unset, 0: Add, 1: Del, 2: Change mode */
224
225        /** Buffer to coalesce the changes together */
226        private StringBuffer m_origBuf;
227
228        private StringBuffer m_newBuf;
229
230        /** Reference to the source string array */
231        private final String[] m_origStrings;
232
233        private ChangeMerger( final StringBuffer sb, final String[] origStrings, final int max ) {
234            m_sb = sb;
235            m_origStrings = origStrings != null ? origStrings.clone() : null;
236            m_max = max;
237
238            m_origBuf = new StringBuffer();
239            m_newBuf = new StringBuffer();
240        }
241
242        private void updateState( final Delta delta ) {
243            m_index++;
244            final Chunk orig = delta.getOriginal();
245            if( orig.first() > m_firstElem ) {
246                // We "skip" some lines in the output.
247                // So flush out the last Change, if one exists.
248                flushChanges();
249
250                // Allow us to "skip" large swaths of unchanged text, show a "limited" amound of
251                // unchanged context so the changes are shown in
252                if( ( orig.first() - m_firstElem ) > 2 * m_unchangedContextLimit ) {
253                    if (m_firstElem > 0) {
254                        final int endIndex = Math.min( m_firstElem + m_unchangedContextLimit, m_origStrings.length -1 );
255
256                        for( int j = m_firstElem; j < endIndex; j++ ) {
257                            m_sb.append( m_origStrings[ j ] );
258                        }
259
260                        m_sb.append( ELIDED_TAIL_INDICATOR_HTML );
261                    }
262
263                    m_sb.append( ELIDED_HEAD_INDICATOR_HTML );
264
265                    final int startIndex = Math.max(orig.first() - m_unchangedContextLimit, 0);
266                    for (int j = startIndex; j < orig.first(); j++) {
267                        m_sb.append( m_origStrings[ j ] );
268                    }
269
270                } else {
271                    // No need to skip anything, just output the whole range...
272                    for( int j = m_firstElem; j < orig.first(); j++ ) {
273                        m_sb.append( m_origStrings[ j ] );
274                    }
275                }
276            }
277            m_firstElem = orig.last() + 1;
278        }
279
280        @Override
281        public void visit( final Revision rev ) {
282            // GNDN (Goes nowhere, does nothing)
283        }
284
285        @Override
286        public void visit( final AddDelta delta ) {
287            updateState( delta );
288
289            // We have run Deletes up to now. Flush them out.
290            if( m_mode == 1 ) {
291                flushChanges();
292                m_mode = -1;
293            }
294            // We are in "neutral mode". Start a new Change
295            if( m_mode == -1 ) {
296                m_mode = 0;
297            }
298
299            // We are in "add mode".
300            if( m_mode == 0 || m_mode == 2 ) {
301                addNew( delta.getRevised() );
302                m_mode = 1;
303            }
304        }
305
306        @Override
307        public void visit( final ChangeDelta delta ) {
308            updateState( delta );
309
310            // We are in "neutral mode". A Change might be merged with an add or delete.
311            if( m_mode == -1 ) {
312                m_mode = 2;
313            }
314
315            // Add the Changes to the buffers.
316            addOrig( delta.getOriginal() );
317            addNew( delta.getRevised() );
318        }
319
320        @Override
321        public void visit( final DeleteDelta delta ) {
322            updateState( delta );
323
324            // We have run Adds up to now. Flush them out.
325            if( m_mode == 0 ) {
326                flushChanges();
327                m_mode = -1;
328            }
329            // We are in "neutral mode". Start a new Change
330            if( m_mode == -1 ) {
331                m_mode = 1;
332            }
333
334            // We are in "delete mode".
335            if( m_mode == 1 || m_mode == 2 ) {
336                addOrig( delta.getOriginal() );
337                m_mode = 1;
338            }
339        }
340
341        public void shutdown() {
342            m_index = m_max + 1; // Make sure that no hyperlink gets created
343            flushChanges();
344
345            if( m_firstElem < m_origStrings.length ) {
346                // If there's more than the limit of the orginal left just emit limit and elided...
347                if( ( m_origStrings.length - m_firstElem ) > m_unchangedContextLimit ) {
348                    final int endIndex = Math.min( m_firstElem + m_unchangedContextLimit, m_origStrings.length -1 );
349                    for (int j = m_firstElem; j < endIndex; j++) {
350                        m_sb.append( m_origStrings[ j ] );
351                    }
352
353                    m_sb.append( ELIDED_TAIL_INDICATOR_HTML );
354                } else {
355                // emit entire tail of original...
356                    for( int j = m_firstElem; j < m_origStrings.length; j++ ) {
357                        m_sb.append( m_origStrings[ j ] );
358                    }
359                }
360            }
361        }
362
363        private void addOrig( final Chunk chunk ) {
364            if( chunk != null ) {
365                chunk.toString( m_origBuf );
366            }
367        }
368
369        private void addNew( final Chunk chunk ) {
370            if( chunk != null ) {
371                chunk.toString( m_newBuf );
372            }
373        }
374
375        private void flushChanges() {
376            if( m_newBuf.length() + m_origBuf.length() > 0 ) {
377                // This is the span element which encapsulates anchor and the change itself
378                m_sb.append( CHANGE_START_HTML );
379
380                // Do we want to have a "back link"?
381                if( m_emitChangeNextPreviousHyperlinks && m_count > 1 ) {
382                    m_sb.append( BACK_PRE_INDEX );
383                    m_sb.append( m_count - 1 );
384                    m_sb.append( BACK_POST_INDEX );
385                }
386
387                // An anchor for the change.
388                if (m_emitChangeNextPreviousHyperlinks) {
389                    m_sb.append( ANCHOR_PRE_INDEX );
390                    m_sb.append( m_count++ );
391                    m_sb.append( ANCHOR_POST_INDEX );
392                }
393
394                // ... has been added
395                if( m_newBuf.length() > 0 ) {
396                    m_sb.append( INSERTION_START_HTML );
397                    m_sb.append( m_newBuf );
398                    m_sb.append( INSERTION_END_HTML );
399                }
400
401                // .. has been removed
402                if( m_origBuf.length() > 0 ) {
403                    m_sb.append( DELETION_START_HTML );
404                    m_sb.append( m_origBuf );
405                    m_sb.append( DELETION_END_HTML );
406                }
407
408                // Do we want a "forward" link?
409                if( m_emitChangeNextPreviousHyperlinks && (m_index < m_max) ) {
410                    m_sb.append( FORWARD_PRE_INDEX );
411                    m_sb.append( m_count ); // Has already been incremented.
412                    m_sb.append( FORWARD_POST_INDEX );
413                }
414
415                m_sb.append( CHANGE_END_HTML );
416
417                // Nuke the buffers.
418                m_origBuf = new StringBuffer();
419                m_newBuf = new StringBuffer();
420            }
421
422            // After a flush, everything is reset.
423            m_mode = -1;
424        }
425    }
426
427}