001package org.hl7.fhir.r5.conformance.profile;
002
003import java.math.BigDecimal;
004import java.util.ArrayList;
005import java.util.HashSet;
006import java.util.List;
007import java.util.Set;
008import java.util.Stack;
009
010import lombok.extern.slf4j.Slf4j;
011import org.hl7.fhir.exceptions.DefinitionException;
012import org.hl7.fhir.exceptions.FHIRException;
013import org.hl7.fhir.r5.conformance.profile.ProfileUtilities.SourcedChildDefinitions;
014import org.hl7.fhir.r5.context.IWorkerContext;
015import org.hl7.fhir.r5.extensions.ExtensionDefinitions;
016import org.hl7.fhir.r5.model.Base;
017import org.hl7.fhir.r5.model.CanonicalType;
018import org.hl7.fhir.r5.model.CodeType;
019import org.hl7.fhir.r5.model.DataType;
020import org.hl7.fhir.r5.model.DateTimeType;
021import org.hl7.fhir.r5.model.ElementDefinition;
022import org.hl7.fhir.r5.model.ElementDefinition.DiscriminatorType;
023import org.hl7.fhir.r5.model.ElementDefinition.ElementDefinitionSlicingComponent;
024import org.hl7.fhir.r5.model.ElementDefinition.ElementDefinitionSlicingDiscriminatorComponent;
025import org.hl7.fhir.r5.model.ElementDefinition.SlicingRules;
026import org.hl7.fhir.r5.model.ElementDefinition.TypeRefComponent;
027import org.hl7.fhir.r5.model.Extension;
028import org.hl7.fhir.r5.model.Property;
029import org.hl7.fhir.r5.model.Quantity;
030import org.hl7.fhir.r5.model.StructureDefinition;
031import org.hl7.fhir.r5.model.StructureDefinition.StructureDefinitionDifferentialComponent;
032import org.hl7.fhir.r5.utils.DefinitionNavigator;
033
034import org.hl7.fhir.r5.utils.TypesUtilities;
035import org.hl7.fhir.r5.utils.UserDataNames;
036import org.hl7.fhir.utilities.CommaSeparatedStringBuilder;
037import org.hl7.fhir.utilities.Utilities;
038import org.hl7.fhir.utilities.i18n.I18nConstants;
039
040/**
041 * when a slice is encountered, it may have additional details defined after the slice that must be merged into 
042 * each of the slices. That's kind of multiple inheritance, and fiendishly complicated to add to the snapshot generator
043 * 
044 * This class pre-processes the differential, finding the slices that have these trailing properties, and 
045 * filling them out in the slices that follow
046 * 
047 * There's potential problems here, mostly around slicing extensions (other kind of slicing isn't allowed)
048 * and also the merging logic might need to be sophisticated.
049 * 
050 */
051@Slf4j
052public class SnapshotGenerationPreProcessor {
053
054  public class ElementAnalysis {
055    private StructureDefinition structure;
056    private ElementDefinition element;
057    private String type;
058    public SourcedChildDefinitions children;
059    protected ElementAnalysis(StructureDefinition structure, ElementDefinition element, String type) {
060      super();
061      this.structure = structure;
062      this.element = element;
063      this.type = type;
064    }
065    public StructureDefinition getStructure() {
066      return structure;
067    }
068    public ElementDefinition getElement() {
069      return element;
070    }
071    public SourcedChildDefinitions getChildren() {
072      return children;
073    }
074    public void setChildren(SourcedChildDefinitions children) {
075      this.children = children;
076    }
077    public String getType() {
078      return type;
079    }
080    public String summary() {
081      return element.getName()+":"+type;
082    }
083  }
084
085  public class SliceInfo {
086    SliceInfo parent;
087    String path;
088    boolean closed;
089    ElementDefinition slicer;
090    List<ElementDefinition> sliceStuff;
091    List<ElementDefinition> slices;
092
093    public SliceInfo(SliceInfo parent, ElementDefinition ed) {
094      this.parent = parent;
095      path = ed.getPath();
096      slicer = ed;
097      sliceStuff = new ArrayList<>();
098      if (parent != null) {
099        parent.add(ed);
100      }
101    }
102
103    public void newSlice(ElementDefinition ed) {
104      if (slices == null) {
105        slices = new ArrayList<ElementDefinition>();
106      }
107      slices.add(ed);
108      if (parent != null) {
109        parent.add(ed);
110      }
111    }
112    public void add(ElementDefinition ed) {
113      if (slices == null) {
114        sliceStuff.add(ed);
115      }      
116      if (parent != null) {
117        parent.add(ed);
118      }
119    }
120  }
121
122  private IWorkerContext context;
123  private ProfileUtilities utils;
124  Set<String> typeNames;
125  private List<SliceInfo> slicings = new ArrayList<>();
126
127  public SnapshotGenerationPreProcessor(ProfileUtilities utils) {
128    super();
129    this.utils = utils;
130    this.context = utils.getContext();
131  }
132
133  public void process(StructureDefinitionDifferentialComponent diff, StructureDefinition srcOriginal) {
134    StructureDefinition srcWrapper = shallowClone(srcOriginal, diff); 
135    processSlices(diff, srcWrapper);  
136    if (srcWrapper.hasExtension(ExtensionDefinitions.EXT_ADDITIONAL_BASE)) {
137       insertMissingSparseElements(diff.getElement(), srcWrapper.getTypeName());
138       for (Extension ext : srcWrapper.getExtensionsByUrl(ExtensionDefinitions.EXT_ADDITIONAL_BASE)) {
139         StructureDefinition ab = context.fetchResource(StructureDefinition.class, ext.getValue().primitiveValue());
140         if (ab == null) {
141           throw new FHIRException("Unable to find additional base '"+ext.getValue().primitiveValue()+"'");
142         }
143         if (!srcWrapper.getType().equals(ab.getType())) {
144           throw new FHIRException("Type mismatch");
145         }
146         SnapshotGenerationPreProcessor abpp = new SnapshotGenerationPreProcessor(utils);
147         abpp.process(ab.getDifferential(), ab);
148         abpp.insertMissingSparseElements(ab.getDifferential().getElement(), srcWrapper.getTypeName());
149         mergeElementsFromAdditionalBase(srcWrapper, ab);         
150       }
151    }
152  }
153  
154  private StructureDefinition shallowClone(StructureDefinition src, StructureDefinitionDifferentialComponent diff) {
155    StructureDefinition sd = new StructureDefinition();
156    sd.setUrl(src.getUrl());
157    sd.setVersion(src.getVersion());
158    sd.setType(src.getType());
159    sd.setDerivation(src.getDerivation());
160    sd.setBaseDefinition(src.getBaseDefinition());
161    sd.setExtension(src.getExtension());
162    sd.setDifferential(diff);
163    return sd;
164  }
165
166  private void mergeElementsFromAdditionalBase(StructureDefinition sourceSD, StructureDefinition baseSD) {
167    List<ElementDefinition> output = new ArrayList<ElementDefinition>();
168    output.add(mergeElementDefinitions(baseSD.getDifferential().getElementFirstRep(), sourceSD.getDifferential().getElementFirstRep(), baseSD));
169    DefinitionNavigator base = new DefinitionNavigator(context, baseSD, true, false);
170    DefinitionNavigator source = new DefinitionNavigator(context, sourceSD, true, false);
171    StructureDefinition sdt = context.fetchTypeDefinition(sourceSD.getType());
172    SourcedChildDefinitions children = utils.getChildMap(sdt, sdt.getSnapshot().getElementFirstRep(), false);
173    mergeElements(output, base, source, children, baseSD);
174    sourceSD.getDifferential().setElement(output);    
175  }
176
177  private void mergeElements(List<ElementDefinition> output, DefinitionNavigator base, DefinitionNavigator source, SourcedChildDefinitions children, StructureDefinition baseSD) {
178    for (ElementDefinition child : children.getList()) {
179      DefinitionNavigator baseChild = base == null ? null : base.childByName(child.getName());
180      DefinitionNavigator sourceChild = source == null ? null : source.childByName(child.getName());
181      if (baseChild != null && sourceChild != null) {
182        if (!baseChild.hasSlices() && !sourceChild.hasSlices()) {
183          output.add(mergeElementDefinitions(baseChild.current(), sourceChild.current(), baseSD));
184          if (sourceChild.hasChildren() || baseChild.hasChildren()) {
185            mergeElements(output, baseChild, sourceChild, getChildren(children, child, sourceChild, baseChild, baseSD), baseSD);
186          }
187        } else if (baseChild.hasSlices() && sourceChild.hasSlices()) {
188          if (!slicingIsConsistent(baseChild.getSlicing(), sourceChild.getSlicing())) {
189            throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, baseSD.getVersionedUrl(), child.getPath()+".slicing", 
190                describeDiscriminators(baseChild.getSlicing()), describeDiscriminators(sourceChild.getSlicing())));                
191          }
192          output.add(mergeElementDefinitions(baseChild.current(), sourceChild.current(), baseSD));
193          mergeElements(output, baseChild, sourceChild, getChildren(children, child, sourceChild, baseChild, baseSD), baseSD);
194          List<DefinitionNavigator> handled = new ArrayList<>();
195          for (DefinitionNavigator slice : sourceChild.slices()) {
196            DefinitionNavigator match = getMatchingSlice(baseChild, slice, sourceChild.getSlicing());
197            if (match != null) {
198              handled.add(match);
199              output.add(mergeElementDefinitions(match.current(), slice.current(), baseSD));
200              mergeElements(output, match, slice, getChildren(children, child, match, slice, baseSD), baseSD);
201            } else {
202              // this slice isn't in the base 
203              output.add(slice.current().copy());
204              mergeElements(output, null, slice, getChildren(children, child, slice, null, baseSD), baseSD);
205            }            
206          }
207          for (DefinitionNavigator slice : baseChild.slices()) {
208            if (!handled.contains(slice)) {
209              output.add(slice.current().copy());
210              mergeElements(output, slice, null, getChildren(children, child, null, slice, baseSD), baseSD);
211            }
212          }          
213        } else  if (baseChild.hasSlices()) {
214          throw new FHIRException("Not done yet");
215        } else { // sourceChild.hasSlices()         
216          throw new FHIRException("Not done yet");
217        }
218      } else if (baseChild != null) {
219        output.add(baseChild.current().copy());
220        if (baseChild.hasChildren()) {
221          mergeElements(output, baseChild, sourceChild, getChildren(children, child, null, baseChild, baseSD), baseSD);
222        }
223        if (baseChild.hasSlices()) {
224          for (DefinitionNavigator slice : baseChild.slices()) {
225            mergeElements(output, slice, null, getChildren(children, child, null, slice, baseSD), baseSD);            
226          }
227        }
228      } else if (sourceChild != null) {
229        output.add(sourceChild.current().copy());
230        if (sourceChild.hasSlices()) {
231          for (DefinitionNavigator slice : sourceChild.slices()) {
232            mergeElements(output, null, slice, getChildren(children, child, slice, null, baseSD), baseSD);            
233          }
234        }
235        if (sourceChild.hasChildren()) {
236          mergeElements(output, baseChild, sourceChild, getChildren(children, child, sourceChild, null, baseSD), baseSD);
237        }
238        // slices
239      } else {
240        // do nothing - no match on either side
241      }
242    }
243  }
244
245  private DefinitionNavigator getMatchingSlice(DefinitionNavigator base, DefinitionNavigator slice, ElementDefinitionSlicingComponent slicing) {
246    List<DataType> values = new ArrayList<>();
247    for (ElementDefinitionSlicingDiscriminatorComponent d : slicing.getDiscriminator()) {
248      values.add(getDiscriminatorValue(slice, d));
249    }
250    DefinitionNavigator match = null;
251    for (DefinitionNavigator t : base.slices()) {
252      List<DataType> values2 = new ArrayList<>();
253      for (ElementDefinitionSlicingDiscriminatorComponent d : slicing.getDiscriminator()) {
254        values2.add(getDiscriminatorValue(t, d));
255      }
256      if (valuesMatch(values, values2)) {
257        if (match == null) {
258          match = t;
259        } else {
260          throw new Error("Duplicate slice");
261        }
262      }      
263    }    
264    return match;
265  }
266
267  private DataType getDiscriminatorValue(DefinitionNavigator slice, ElementDefinitionSlicingDiscriminatorComponent d) {
268    // we're not following types, because we want to stop where the differential stops. but right here and now,
269    // we have to follow the types. So we're going to clone the navigator 
270    DefinitionNavigator dn = new DefinitionNavigator(slice, true);
271    switch (d.getType() ) {
272    case EXISTS:
273      throw new Error("Not supported yet");
274    case NULL:
275      throw new Error("Not supported yet");
276    case PATTERN:
277      throw new Error("Not supported yet");
278    case POSITION:
279      throw new Error("Not supported yet");
280    case PROFILE:
281      throw new Error("Not supported yet");
282    case TYPE:
283      if ("$this".equals(d.getPath())) {
284        return new CodeType(dn.getManualType() != null ? dn.getManualType().getCode() : dn.current().typeSummary());
285      } else {
286        throw new Error("Not supported yet");
287      }
288    case VALUE:
289      DefinitionNavigator child = dn.childByName(d.getPath());
290      if (child != null) {
291        ElementDefinition ed = child.current();
292        if (ed.hasFixed()) {
293          return ed.getFixed();
294        } else if (ed.hasPattern()) {
295          return ed.getPattern();
296        }
297      } else {
298        return null;
299      }
300    default:
301      throw new Error("Not supported yet");    
302    }
303  }
304
305  private boolean valuesMatch(List<DataType> values1, List<DataType> values2) {
306    for (int i = 0; i < values1.size(); i++) {
307      DataType v1 = values1.get(i);
308      DataType v2 = values2.get(i);
309      if (!valuesMatch(v1, v2)) {
310        return false;
311      }
312    }
313    return true;
314  }
315
316  private boolean valuesMatch(DataType v1, DataType v2) {
317    if (v1 == null && v2 == null) {
318      return true;
319    } else if (v1 != null && v2 != null) {
320      return v1.equalsDeep(v2);
321    } else {
322      return false;
323    }
324  }
325
326  private boolean slicingIsConsistent(ElementDefinitionSlicingComponent src, ElementDefinitionSlicingComponent base) {
327    if (src.getRules() != base.getRules()) {
328      return false;
329    }
330    if (src.getDiscriminator().size() != base.getDiscriminator().size()) {
331      return false;
332    }
333    for (ElementDefinitionSlicingDiscriminatorComponent d1 : src.getDiscriminator()) {
334      boolean found = false;
335      for (ElementDefinitionSlicingDiscriminatorComponent d2 : base.getDiscriminator()) {
336        found = found || (d1.getType() == d2.getType() && d1.getPath().equals(d2.getPath()));
337      }
338      if (!found) {
339        return false;
340      }
341    }
342    return true;
343  }
344
345  private Object describeDiscriminators(ElementDefinitionSlicingComponent slicing) {
346    CommaSeparatedStringBuilder b = new CommaSeparatedStringBuilder();    
347    for (ElementDefinitionSlicingDiscriminatorComponent t : slicing.getDiscriminator()) {
348      b.append(t.getType().toCode()+":"+t.getPath());
349    }
350    return (slicing.hasRules() ? slicing.getRules().toCode()+":" : "")+b.toString()+(slicing.hasOrdered() ? " (ordered)" : "");
351  }
352
353  private SourcedChildDefinitions getChildren(SourcedChildDefinitions children, ElementDefinition child, DefinitionNavigator source, DefinitionNavigator base, StructureDefinition baseSD) {
354    if (child.getType().size() > 1) {
355      String type = null;
356      if (source != null && base != null) {
357        String typeSource = statedOrImpliedType(source);
358        String typeBase = statedOrImpliedType(base);
359        if (typeSource != null && typeBase != null) {
360          if (typeSource.equals(typeBase)) {
361            type = typeSource;
362          } else {
363            throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, baseSD.getVersionedUrl(), child.getPath()+".type", typeSource, typeBase));
364          }
365        } else if (typeSource != null) {
366          type = typeSource;
367        } else if (typeBase != null) {
368          type = typeBase;          
369        }
370      } else if (source != null) {
371        type = statedOrImpliedType(source);       
372      } else if (base != null) {
373        type = statedOrImpliedType(base);        
374      } else {
375        // type = "DataType";
376      }
377      if (type == null) {          
378        throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INDETERMINATE_TYPE, baseSD.getVersionedUrl(), child.getPath()+".type"));
379        
380      } else {
381        return utils.getChildMap(children.getSource(), child, true, type);
382      }
383    } else {
384      return utils.getChildMap(children.getSource(), child, true);
385    }
386  }
387
388  private String statedOrImpliedType(DefinitionNavigator source) {
389    if (source.getManualType() != null) {
390      return source.getManualType().getCode();
391    } else if (source.current().getType().size() == 1) {
392      return source.current().getTypeFirstRep().getCode();
393    } else {
394      return null;
395    }
396  }
397
398  private ElementDefinition mergeElementDefinitions(ElementDefinition base, ElementDefinition source, StructureDefinition baseSD) {
399    ElementDefinition merged = new ElementDefinition();
400    merged.setPath(source.getPath());
401    if (source.hasSlicing()) {
402      merged.setSlicing(source.getSlicing());
403    }
404    
405    merged.setLabelElement(chooseProp(source.getLabelElement(),  base.getLabelElement()));
406    merged.setShortElement(chooseProp(source.getShortElement(), base.getShortElement()));
407    merged.setDefinitionElement(chooseProp(source.getDefinitionElement(), base.getDefinitionElement()));
408    merged.setCommentElement(chooseProp(source.getCommentElement(), base.getCommentElement()));
409    merged.setRequirementsElement(chooseProp(source.getRequirementsElement(), base.getRequirementsElement()));
410    merged.setMeaningWhenMissingElement(chooseProp(source.getMeaningWhenMissingElement(), base.getMeaningWhenMissingElement()));
411    merged.setOrderMeaningElement(chooseProp(source.getOrderMeaningElement(), base.getOrderMeaningElement()));
412    merged.setMaxLengthElement(chooseProp(source.getMaxLengthElement(), base.getMaxLengthElement()));
413    merged.setMustHaveValueElement(chooseProp( source.getMustHaveValueElement(), base.getMustHaveValueElement()));
414    merged.setMustSupportElement(chooseProp(source.getMustSupportElement(), base.getMustSupportElement()));
415    merged.setIsModifierElement(chooseProp(source.getIsModifierElement(), base.getIsModifierElement()));
416    merged.setIsModifierReasonElement(chooseProp(source.getIsModifierReasonElement(), base.getIsModifierReasonElement()));
417    merged.setIsSummaryElement(chooseProp(source.getIsSummaryElement(), base.getIsSummaryElement()));
418
419    if (source.hasMin() && base.hasMin()) {
420      merged.setMinElement(source.getMin() < base.getMin() ? source.getMinElement().copy() : base.getMinElement().copy());      
421    } else {
422      merged.setMinElement(chooseProp(source.getMinElement(), base.getMinElement().copy()));
423    }
424    if (source.hasMax() && base.hasMax()) {
425      merged.setMaxElement(source.getMaxAsInt() < base.getMaxAsInt() ? source.getMaxElement().copy() : base.getMaxElement().copy());      
426    } else {
427      merged.setMaxElement(chooseProp(source.getMaxElement(), base.getMaxElement()));
428    }
429    
430    if (source.hasFixed() || base.hasFixed()) {
431      if (source.hasFixed()) {
432        if (base.hasFixed()) {
433          if (!source.getFixed().equalsDeep(base.getFixed())) {            
434            throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, baseSD.getVersionedUrl(), source.getPath()+".fixed", source.getFixed().toString(), base.getFixed().toString()));
435          } else {
436            merged.setFixed(source.getFixed().copy());          
437          }
438        } else if (base.hasPattern()) {
439          merged.setFixed(checkPatternValues(baseSD.getVersionedUrl(), source.getPath()+".fixed", source.getFixed(), base.getPattern(), false)); 
440        } else {
441          merged.setFixed(source.getFixed().copy());          
442        }
443      } else if (source.hasPattern()) { // base.hasFixed() == true
444        merged.setFixed(checkPatternValues(baseSD.getVersionedUrl(), source.getPath()+".pattern", base.getFixed(), source.getPattern(), false)); 
445      } else {
446        merged.setFixed(base.getFixed().copy());          
447      }
448    } else if (source.hasPattern() && base.hasPattern()) {
449      merged.setPattern(checkPatternValues(baseSD.getVersionedUrl(), source.getPath()+".pattern", source.getFixed(), base.getFixed(), true));
450    } else {
451      merged.setPattern(chooseProp(source.getPattern(), base.getPattern()));
452    }
453    
454    if (source.hasMinValue() && base.hasMinValue()) {
455      merged.setMinValue(isLower(baseSD.getVersionedUrl(), source.getPath(), "minValue", source.getMinValue(), base.getMinValue()) ? base.getMinValue().copy() : source.getMinValue().copy());      
456    } else {
457      merged.setMinValue(chooseProp(source.getMinValue(), base.getMinValue()));
458    }
459    if (source.hasMaxValue() && base.hasMaxValue()) {
460      merged.setMaxValue(isLower(baseSD.getVersionedUrl(), source.getPath(), "maxValue", source.getMaxValue(), base.getMaxValue()) ? source.getMaxValue().copy() : base.getMaxValue().copy());            
461    } else {
462      merged.setMaxValue(chooseProp(source.getMaxValue(), base.getMaxValue()));
463    }
464    if (source.hasMaxLength() && base.hasMaxLength()) {
465      merged.setMaxLengthElement(base.getMaxLength() < source.getMaxLength() ? source.getMaxLengthElement().copy() : base.getMaxLengthElement().copy());            
466    } else {
467      merged.setMaxLengthElement(chooseProp(source.getMaxLengthElement(), base.getMaxLengthElement().copy()));
468    }
469    // union
470    union(merged.getAlias(), source.getAlias(), base.getAlias());
471    union(merged.getCode(), source.getCode(), base.getCode());
472    union(merged.getExample(), source.getExample(), base.getExample());
473    union(merged.getConstraint(), source.getConstraint(), base.getConstraint());
474    union(merged.getMapping(), source.getMapping(), base.getMapping());
475
476    // intersection
477    if (source.hasValueAlternatives() && base.hasValueAlternatives()) {
478      for (CanonicalType st : source.getValueAlternatives()) {
479        boolean exists = false;
480        for (CanonicalType st2 : base.getValueAlternatives()) {
481          exists = exists || st.equals(st2);
482        }
483        if (exists) {
484          merged.getValueAlternatives().add(st.copy());
485        }
486      }
487    } else if (source.hasValueAlternatives()) {
488      for (CanonicalType st : source.getValueAlternatives()) {
489        merged.getValueAlternatives().add(st.copy());
490      }
491    } else if (base.hasValueAlternatives()) {
492      for (CanonicalType st : base.getValueAlternatives()) {
493        merged.getValueAlternatives().add(st.copy());
494      }
495    }
496
497    if (source.hasType() && base.hasType()) {
498      for (TypeRefComponent t1 : source.getType()) {
499        for (TypeRefComponent t2 : base.getType()) {
500          if (Utilities.stringsEqual(t1.getWorkingCode(), t2.getWorkingCode())) {
501            merged.getType().add(mergeTypes(baseSD.getVersionedUrl(), source.getPath(), t1, t2));
502          }
503        }
504      }
505      if (merged.getType().isEmpty()) {
506        throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, baseSD.getVersionedUrl(), source.getPath()+".type", source.typeSummary(), base.typeSummary()));
507        
508      }
509    } else if (source.hasType()) {
510      for (TypeRefComponent st : source.getType()) {
511        merged.getType().add(st.copy());
512      }
513    } else if (base.hasType()) {
514      for (TypeRefComponent st : base.getType()) {
515        merged.getType().add(st.copy());
516      }
517    }
518
519    // binding
520    if (source.hasBinding() && base.hasBinding()) {
521      throw new Error("not done yet");
522    } else if (source.hasBinding()) {
523      merged.setBinding(source.getBinding().copy());
524    } else if (base.hasBinding()) {
525      merged.setBinding(base.getBinding().copy());
526    }
527    
528    
529    return merged;
530  }
531
532  private <T extends DataType> T chooseProp(T source, T base) {
533    if (source != null && !source.isEmpty()) {
534      return (T) source.copy();
535    }
536    if (base != null && !base.isEmpty()) {
537      return (T) base.copy();
538    }
539    return null;
540  }
541
542  private TypeRefComponent mergeTypes(String vurl, String path, TypeRefComponent t1, TypeRefComponent t2) {
543    TypeRefComponent tr = t1.copy();
544    if (t1.hasProfile() && t2.hasProfile()) {
545      // here, this is tricky, because we need to know what the merged additional bases of the pairings will be
546      if (t1.getProfile().size() > 1 || t2.getProfile().size() > 1) {
547        throw new FHIRException("Not handled yet: multiple profiles");        
548      }
549      StructureDefinition sd1 = context.fetchResource(StructureDefinition.class, t1.getProfile().get(0).asStringValue());
550      if (sd1 == null) {
551        throw new FHIRException("Unknown type profile at '"+path+"': "+t1.getProfile().get(0).asStringValue());                
552      }
553      StructureDefinition sd2 = context.fetchResource(StructureDefinition.class, t2.getProfile().get(0).asStringValue());
554      if (sd2 == null) {
555        throw new FHIRException("Unknown type profile at '"+path+"': "+t2.getProfile().get(0).asStringValue());                
556      }
557      tr.getProfile().clear();
558      if (specialises(sd1, sd2)) { 
559        // both sd1 and sd2 apply, but sd1 applies everything in sd2, so it's just sd1
560        tr.getProfile().add(t1.getProfile().get(0).copy());
561      } else if (specialises(sd2, sd1)) { 
562        // both sd1 and sd2 apply, but sd2 applies everything in sd1, so it's just sd2
563        tr.getProfile().add(t2.getProfile().get(0).copy());
564      } else {
565        // oh dear. We have to find a type that is both of them 
566        StructureDefinition sd3 = findJointProfile(sd1, sd2);
567        if (sd3 == null) {
568          throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_NO_TYPE, vurl, path, sd1.getVersionedUrl(), sd2.getVersionedUrl()));
569        } else {
570          tr.getProfile().add(new CanonicalType(sd3.getUrl()));          
571        }
572      }
573    } else if (t2.hasProfile()) {
574      for (CanonicalType ct : t2.getProfile()) {
575        tr.getProfile().add(ct.copy());
576      }
577    }
578    if (t1.hasTargetProfile() && t2.hasTargetProfile()) {
579      // here, this is tricky, because we need to know what the merged additional bases of the pairings will be
580    } else if (t2.hasTargetProfile()) {
581      for (CanonicalType ct : t2.getTargetProfile()) {
582        tr.getTargetProfile().add(ct.copy());
583      }
584    }
585    if (t1.hasAggregation() && t2.hasAggregation() && !t1.getAggregation().equals(t2.getAggregation())) {
586      throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path+".type["+tr.getWorkingCode()+"].aggregation", t1.getAggregation(), t2.getAggregation()));
587    }
588    if (t1.hasVersioning() && t2.hasVersioning() && t1.getVersioning() != t2.getVersioning()) {
589      throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path+".type["+tr.getWorkingCode()+"].aggregation", t1.getVersioning(), t2.getVersioning()));
590    }
591    return tr;
592  }
593
594  private StructureDefinition findJointProfile(StructureDefinition sd1, StructureDefinition sd2) {
595    for (StructureDefinition sd : context.fetchResourcesByType(StructureDefinition.class)) {
596      boolean b1 = sd.getBaseDefinitions().contains(sd1.getUrl()) || sd.getBaseDefinitions().contains(sd1.getVersionedUrl());
597      boolean b2 = sd.getBaseDefinitions().contains(sd2.getUrl()) || sd.getBaseDefinitions().contains(sd2.getVersionedUrl());
598      if (b1 && b2) {
599        return sd;
600      }
601    }
602    return null;
603  }
604
605  private boolean specialises(StructureDefinition focus, StructureDefinition other) {
606    // we ignore impose and compliesWith - for now?
607    for (String url : focus.getBaseDefinitions()) {
608      StructureDefinition base = context.fetchResource(StructureDefinition.class, url);
609      if (base != null) {
610        if (base == other || specialises(base, other)) {
611          return true;
612        }
613      }
614    }
615    return false;
616  }
617
618  private <T extends Base> void union(List<T> merged, List<T> source, List<T> base) {
619    for (T st : source) {
620      merged.add((T) st.copy());
621    }
622    for (T st : base) {
623      boolean exists = false;
624      for (T st2 : merged) {
625        exists = exists || st.equals(st2);
626      }
627      if (!exists) {
628        merged.add((T) st.copy());        
629      }
630    }
631  }
632
633  private boolean isLower(String vurl, String path, String property, DataType v1, DataType v2) {
634    if (v1 instanceof Quantity && v2 instanceof Quantity) {
635      Quantity q1 = (Quantity) v1;
636      Quantity q2 = (Quantity) v2;
637      if (q1.hasUnit() || q2.hasUnit()) {
638        if (Utilities.stringsEqual(q1.getUnit(), q2.getUnit())) {
639          throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path+"."+property+".unit", v1.fhirType(), v2.fhirType()));
640        }
641      }
642      return isLower(vurl, path, property+".value", q1.getValueElement(), q2.getValueElement());
643    } else if (v1.isDateTime() && v2.isDateTime()) {
644      DateTimeType d1 = (DateTimeType) v1;
645      DateTimeType d2 = (DateTimeType) v2;
646      return d1.before(d2);      
647    } else if (Utilities.isDecimal(v1.primitiveValue(), true) && Utilities.isDecimal(v2.primitiveValue(), true)) {
648      BigDecimal d1 = new BigDecimal(v1.primitiveValue());
649      BigDecimal d2 = new BigDecimal(v2.primitiveValue());
650      return d1.compareTo(d2) < 0;
651    } else {
652      throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path+"."+property, v1.fhirType(), v2.fhirType()));
653    }
654  }
655
656  private DataType checkPatternValues(String vurl, String path, DataType v1, DataType v2, boolean extras) {
657    if (!v1.fhirType().equals(v2.fhirType())) {
658      throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path, v1.fhirType(), v2.fhirType()));
659    }
660    DataType merged = v1.copy();
661    if (v1.isPrimitive()) {
662      if (!Utilities.stringsEqual(v1.primitiveValue(), v2.primitiveValue())) {
663        throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path+".value", v1.primitiveValue(), v2.primitiveValue()));        
664      }
665    }
666    for (Property p1 : v1.children()) {
667      Property p2 = v2.getChildByName(p1.getName());
668      if (p1.hasValues() && p2.hasValues()) {
669        if (p1.getValues().size() > 1 || p1.getValues().size() > 2) {
670          throw new Error("Not supported");          
671        }
672        merged.setProperty(p1.getName(), checkPatternValues(vurl, path+"."+p1.getName(), (DataType) p1.getValues().get(0), (DataType) p2.getValues().get(0), extras));
673      } else if (p2.hasValues()) {
674        if (!extras) {
675          throw new FHIRException(context.formatMessage(I18nConstants.SD_ADDITIONAL_BASE_INCOMPATIBLE_VALUES, vurl, path+"."+p1.getName(), "null", v2.primitiveValue()));            
676        }
677        if (p2.getValues().size() > 1) {
678          throw new Error("Not supported");
679        }
680        merged.setProperty(p1.getName(), p2.getValues().get(0).copy());
681      }
682    }
683    return merged;
684  }
685
686
687  private void processSlices(StructureDefinitionDifferentialComponent diff, StructureDefinition src) {
688    // first pass, divide it up 
689    for (int cursor = 0; cursor < diff.getElement().size(); cursor++) {      
690      ElementDefinition ed = diff.getElement().get(cursor);
691
692      SliceInfo si = getSlicing(ed);
693      if (si == null) {
694        if (ed.hasSlicing() && !isExtensionSlicing(ed)) {
695          si = new SliceInfo(null, ed);
696          slicings.add(si);
697        } else {
698          // ignore this
699        }
700      } else {
701        if (ed.hasSliceName() && ed.getPath().equals(si.path)) {
702          si.newSlice(ed);
703        } else if (ed.hasSlicing() && !isExtensionSlicing(ed)) {
704          si = new SliceInfo(si, ed);
705          slicings.add(si);
706        } else {
707          si.add(ed);
708        }
709      }
710    }       
711
712    for (SliceInfo si : slicings) {
713      if (!si.sliceStuff.isEmpty() && si.slices != null) {
714        for (ElementDefinition ed : si.sliceStuff) {
715          if (ed.hasSlicing() && !isExtensionSlicing(ed)) {
716            String message = context.formatMessage(I18nConstants.UNSUPPORTED_SLICING_COMPLEXITY, si.slicer.getPath(), ed.getPath(), ed.getSlicing().summary());
717            log.warn(message);
718            return;
719          }
720        }
721      }
722    }
723
724    // working backward
725    for (int i = slicings.size() - 1; i >= 0; i--) {
726      SliceInfo si = slicings.get(i);
727      if (!si.sliceStuff.isEmpty() && si.slices != null) {
728        // for each actual slice, we need to merge sliceStuff in
729        for (ElementDefinition slice : si.slices) {
730          mergeElements(diff.getElement(), si.sliceStuff, slice, si.slicer);
731        }
732      } else {
733        // we just ignore these - nothing to do
734      }
735    }
736
737    for (ElementDefinition ed : diff.getElement()) {
738      ProfileUtilities.markExtensions(ed, false, src);
739    }
740  }
741
742  private void mergeElements(List<ElementDefinition> elements, List<ElementDefinition> allSlices, ElementDefinition slice, ElementDefinition slicer) {
743    // we have
744    //   elements - the list of all the elements
745    //   allSlices which is the content defined for all the slices
746    //   slice -the anchor element for the slice
747
748    int sliceIndex = elements.indexOf(slice);
749    int startOfSlice = sliceIndex + 1;
750    int endOfSlice = findEndOfSlice(elements, slice);
751
752    Set<String> missing = new HashSet<>();
753    // the simple case is that all the stuff in allSlices exists between startOfSlice and endOfSlice
754    boolean allFound = true;
755    for (int i = 0; i < allSlices.size(); i++) {
756      boolean found = false;
757      for (int j = startOfSlice; j <= endOfSlice; j++) {
758        if (elementsMatch(elements.get(j), allSlices.get(i))) {
759          found = true;
760          break;
761        }
762      }
763      if (!found) {
764        missing.add(allSlices.get(i).getPath());
765        allFound = false;
766      }
767    }
768
769    if (allFound) {
770      // then we just merge it in
771      for (int j = startOfSlice; j <= endOfSlice; j++) {
772        for (int i = 0; i < allSlices.size(); i++) {
773          if (elementsMatch(elements.get(j), allSlices.get(i))) {
774            merge(elements.get(j), allSlices.get(i));
775          }
776        }
777      }
778    } else {
779      Set<ElementDefinition> handled = new HashSet<>();
780
781      // merge the simple stuff
782      for (int j = startOfSlice; j <= endOfSlice; j++) {
783        for (int i = 0; i < allSlices.size(); i++) {
784          if (elementsMatch(elements.get(j), allSlices.get(i))) {
785            handled.add(allSlices.get(i));
786            merge(elements.get(j), allSlices.get(i));
787          }
788        }
789      }
790
791      // we have a lot of work to do
792      // the challenge is that the things missing from startOfSlice..endOfSlice have to injected in the correct order 
793      // which means that we need to know the definitions
794      // and is extra tricky because we're sparse. so we just use the stated path
795      for (ElementDefinition ed : allSlices) {
796        if (!handled.contains(ed)) {
797          List<ElementAnalysis> edDef = analysePath(ed);
798          String id = ed.getId().replace(slicer.getId(), slice.getId());
799          int index = determineInsertionPoint(elements, startOfSlice, endOfSlice, id, ed.getPath(), edDef);
800          ElementDefinition edc = ed.copy();
801          edc.setUserData(UserDataNames.SNAPSHOT_PREPROCESS_INJECTED, true);
802          edc.setId(id);
803          elements.add(index, edc);
804          endOfSlice++;
805        }
806      }
807    }   
808
809  }
810
811  private boolean elementsMatch(ElementDefinition ed1, ElementDefinition ed2) {
812    if (!pathsMatch(ed1.getPath(), ed2.getPath())) {
813      return false;
814    } else if (ed1.getSliceName() != null && ed2.getSliceName() != null) {
815      return ed1.getSliceName().equals(ed2.getSliceName());
816    } else  if (ed1.getSliceName() != null || ed2.getSliceName() != null) {
817      return false;
818    } else {
819      return true;
820    }
821  }
822
823  private boolean pathsMatch(String path1, String path2) {
824    if (path1.equals(path2)) {
825      return true;
826    }
827    if (path1.endsWith("[x]")) {
828      path1 = path1.substring(0, path1.length()-3);
829      if (path2.startsWith(path1)) {
830        if (!path2.substring(path1.length()).contains(".")) {
831          return true;
832        }
833      }
834    }
835    if (path2.endsWith("[x]")) {
836      path2 = path2.substring(0, path2.length()-3);
837      if (path1.startsWith(path2)) {
838        if (!path1.substring(path2.length()).contains(".")) {
839          return true;
840        }
841      }
842    }
843    return false;
844  }
845
846  private int determineInsertionPoint(List<ElementDefinition> elements, int startOfSlice, int endOfSlice, String id, String path, List<ElementAnalysis> edDef) {
847    // we work backwards through the id, looking for peers (this is the only way we can manage slicing)
848    String[] p = id.split("\\.");
849    for (int i = p.length-1; i >= 1; i--) {
850      String subId = p[0];
851      for (int j = 1; j <= i; j++) {
852        subId += "."+p[j];
853      }
854      List<ElementDefinition> peers = findPeers(elements, startOfSlice, endOfSlice, subId);
855      if (!peers.isEmpty()) {
856        // Once we find some, we figure out the insertion point - before one of them, or after the last? 
857        for (ElementDefinition ed : peers) {
858          if (comesAfterThis(id, path, edDef, ed)) {
859            return elements.indexOf(ed);
860          }
861        }
862        return elements.indexOf(peers.get(peers.size() -1))+1;
863      }
864    }
865    return endOfSlice+1;
866  }
867
868  private List<ElementDefinition> findPeers(List<ElementDefinition> elements, int startOfSlice, int endOfSlice, String subId) {
869    List<ElementDefinition> peers =  new ArrayList<>();
870    for (int i = startOfSlice; i <= endOfSlice; i++) {
871      ElementDefinition ed = elements.get(i);
872      if (ed.getId().startsWith(subId)) {
873        peers.add(ed);
874      }
875    }
876    return peers;
877  }
878
879  private String summary(List<ElementAnalysis> edDef) {
880    List<String> s = new ArrayList<>();
881    for (ElementAnalysis ed : edDef) {
882      s.add(ed.summary());
883    }
884
885    return CommaSeparatedStringBuilder.join(",", s);
886  }
887
888  private boolean comesAfterThis(String id, String path, List<ElementAnalysis> edDef, ElementDefinition ed) {
889    String[] p1 = id.split("\\.");
890    String[] p2 = ed.getId().split("\\.");
891    for (int i = 0; i < Integer.min(p1.length,  p2.length); i++) {
892      if (!p1[i].equals(p2[i])) {
893        ElementAnalysis sed = edDef.get(i-1);
894        int i1 = indexOfName(sed, p1[i]);
895        int i2 = indexOfName(sed, p2[i]);
896        if (i == Integer.min(p1.length,  p2.length) -1 && i1 == i2) {
897          if (!p1[i].contains(":") && p2[i].contains(":")) {
898            // launched straight into slicing without setting it up, 
899            // and now it's being set up 
900            return true;
901          }
902        }
903        return i1 < i2;
904      } else {
905        // well, we just go on
906      }
907    }
908    return p1.length < p2.length;
909  }
910
911  private int indexOfName(ElementAnalysis sed, String name) {
912    if (name.contains(":")) {
913      name = name.substring(0, name.indexOf(":"));
914    }
915    for (int i = 0; i < sed.getChildren().getList().size(); i++) {
916      if (name.equals(sed.getChildren().getList().get(i).getName())) {
917        return i;
918      }      
919    }
920    return -1;
921  }
922
923  private List<ElementAnalysis> analysePath(ElementDefinition ed) {
924    List<ElementAnalysis> res = new ArrayList<>();
925    for (String pn : ed.getPath().split("\\.")) {
926      analysePathSegment(ed, res, pn);
927    }
928    return res;
929  }
930
931  private void analysePathSegment(ElementDefinition ed, List<ElementAnalysis> res, String pn) {
932    if (res.isEmpty()) {
933      StructureDefinition sd = context.fetchTypeDefinition(pn);
934      if (sd == null) {
935        String message = context.formatMessage(I18nConstants.UNKNOWN_TYPE__AT_, pn, ed.getId());
936        throw new DefinitionException(message);
937      }
938      res.add(new ElementAnalysis(sd, sd.getSnapshot().getElementFirstRep(), null));
939    } else {
940      ElementAnalysis sed = res.get(res.size()-1);
941      sed.setChildren(utils.getChildMap(sed.getStructure(), sed.getElement(), true, sed.getType()));
942      ElementDefinition t = null;
943      String type = null;
944      for (ElementDefinition child : sed.getChildren().getList()) {
945        if (pn.equals(child.getName())) {
946          t = child;
947          break;
948        }
949        if (child.getName().endsWith("[x]")) {
950          String rn = child.getName().substring(0, child.getName().length()-3);
951          if (pn.startsWith(rn)) {
952            t = child;
953            String tn = pn.substring(rn.length());
954            if (TypesUtilities.isPrimitive(Utilities.uncapitalize(tn))) {
955              type = Utilities.uncapitalize(tn);
956            } else {
957              type = tn;
958            }
959            break;
960          }
961        }
962      }
963      if (t == null) {
964        String message = context.formatMessage(I18nConstants.UNKNOWN_PROPERTY, pn, ed.getPath());
965        throw new DefinitionException("Unknown path "+pn+" in path "+ed.getPath()+": "+message);          
966      } else {
967        res.add(new ElementAnalysis(sed.getChildren().getSource(), t, type));
968      }
969    }
970  }
971
972  private int findEndOfSlice(List<ElementDefinition> elements, ElementDefinition slice) {
973    for (int i = elements.indexOf(slice); i < elements.size(); i++) {
974      ElementDefinition e = elements.get(i);
975      if (!(e.getPath().startsWith(slice.getPath()+".") ||
976          (e.getPath().equals(slice.getPath()) && slice.getSliceName().equals(e.getSliceName())))) {
977        return i-1;
978      }
979    }
980    return elements.size() - 1;
981  }
982
983  private void merge(ElementDefinition focus, ElementDefinition base) {
984    if (base.hasLabel() && !focus.hasLabel()) {
985      focus.setLabelElement(base.getLabelElement());
986    }    
987    if (base.hasCode() && !focus.hasCode()) {
988      focus.getCode().addAll(base.getCode());
989    }
990    if (base.hasShort() && !focus.hasShort()) {
991      focus.setShortElement(base.getShortElement());
992    }    
993    if (base.hasDefinition() && !focus.hasDefinition()) {
994      focus.setDefinitionElement(base.getDefinitionElement());
995    }    
996    if (base.hasComment() && !focus.hasComment()) {
997      focus.setCommentElement(base.getCommentElement());
998    }    
999    if (base.hasRequirements() && !focus.hasRequirements()) {
1000      focus.setRequirementsElement(base.getRequirementsElement());
1001    }    
1002    if (base.hasAlias() && !focus.hasAlias()) {
1003      focus.getAlias().addAll(base.getAlias());
1004    }
1005    if (base.hasMin() && !focus.hasMin()) {
1006      focus.setMinElement(base.getMinElement());
1007    }    
1008    if (base.hasMax() && !focus.hasMax()) {
1009      focus.setMaxElement(base.getMaxElement());
1010    }    
1011    if (base.hasType() && !focus.hasType()) {
1012      focus.getType().addAll(base.getType());
1013    }
1014    if (base.hasDefaultValue() && !focus.hasDefaultValue()) {
1015      focus.setDefaultValue(base.getDefaultValue());
1016    }
1017    if (base.hasMeaningWhenMissing() && !focus.hasMeaningWhenMissing()) {
1018      focus.setMeaningWhenMissingElement(base.getMeaningWhenMissingElement());
1019    }    
1020    if (base.hasOrderMeaning() && !focus.hasOrderMeaning()) {
1021      focus.setOrderMeaningElement(base.getOrderMeaningElement());
1022    }    
1023    if (base.hasFixed() && !focus.hasFixed()) {
1024      focus.setFixed(base.getFixed());
1025    }
1026    if (base.hasPattern() && !focus.hasPattern()) {
1027      focus.setPattern(base.getPattern());
1028    }
1029    if (base.hasExample() && !focus.hasExample()) {
1030      focus.getExample().addAll(base.getExample());
1031    }
1032    if (base.hasMinValue() && !focus.hasMinValue()) {
1033      focus.setMinValue(base.getMinValue());
1034    }
1035    if (base.hasMaxValue() && !focus.hasMaxValue()) {
1036      focus.setMaxValue(base.getMaxValue());
1037    }
1038    if (base.hasMaxLength() && !focus.hasMaxLength()) {
1039      focus.setMaxLengthElement(base.getMaxLengthElement());
1040    }    
1041    if (base.hasConstraint() && !focus.hasConstraint()) {
1042      focus.getConstraint().addAll(base.getConstraint());
1043    }
1044    if (base.hasMustHaveValue() && !focus.hasMustHaveValue()) {
1045      focus.setMustHaveValueElement(base.getMustHaveValueElement());
1046    }    
1047    if (base.hasValueAlternatives() && !focus.hasValueAlternatives()) {
1048      focus.getValueAlternatives().addAll(base.getValueAlternatives());
1049    }
1050    if (base.hasMustSupport() && !focus.hasMustSupport()) {
1051      focus.setMustSupportElement(base.getMustSupportElement());
1052    }    
1053    if (base.hasIsModifier() && !focus.hasIsModifier()) {
1054      focus.setIsModifierElement(base.getIsModifierElement());
1055    }    
1056    if (base.hasIsModifierReason() && !focus.hasIsModifierReason()) {
1057      focus.setIsModifierReasonElement(base.getIsModifierReasonElement());
1058    }    
1059    if (base.hasIsSummary() && !focus.hasIsSummary()) {
1060      focus.setIsSummaryElement(base.getIsSummaryElement());
1061    }    
1062    if (base.hasBinding() && !focus.hasBinding()) {
1063      focus.setBinding(base.getBinding());
1064    }
1065  }
1066
1067  private boolean isExtensionSlicing(ElementDefinition ed) {
1068    if (!Utilities.existsInList(ed.getName(), "extension", "modiferExtension")) {
1069      return false;
1070    }
1071    if (ed.getSlicing().getRules() != SlicingRules.OPEN || (!ed.getSlicing().hasOrdered() || ed.getSlicing().getOrdered()) || ed.getSlicing().getDiscriminator().size() != 1) {
1072      return false;
1073    }
1074    ElementDefinitionSlicingDiscriminatorComponent d = ed.getSlicing().getDiscriminatorFirstRep();
1075    return d.getType() == DiscriminatorType.VALUE && "url".equals(d.getPath());
1076  }
1077
1078  private SliceInfo getSlicing(ElementDefinition ed) {
1079    for (int i = slicings.size() - 1; i >= 0; i--) {
1080      SliceInfo si = slicings.get(i);
1081      if (!si.closed) {
1082        if (si.path.length() > ed.getPath().length()) {
1083          si.closed = true;
1084        } else if (ed.getPath().startsWith(si.path)) {
1085          return si;
1086        }
1087      }
1088    }
1089    return null;
1090  }
1091
1092  public List<ElementDefinition> supplementMissingDiffElements(StructureDefinition profile) { 
1093    List<ElementDefinition> list = new ArrayList<>(); 
1094    list.addAll(profile.getDifferential().getElement()); 
1095    if (list.isEmpty()) { 
1096      ElementDefinition root = new ElementDefinition().setPath(profile.getTypeName()); 
1097      root.setId(profile.getTypeName()); 
1098      list.add(root); 
1099    } else { 
1100      if (list.get(0).getPath().contains(".")) { 
1101        ElementDefinition root = new ElementDefinition().setPath(profile.getTypeName()); 
1102        root.setId(profile.getTypeName()); 
1103        list.add(0, root); 
1104      } 
1105    } 
1106    insertMissingSparseElements(list, profile.getTypeName()); 
1107    return list; 
1108  } 
1109
1110  private void insertMissingSparseElements(List<ElementDefinition> list, String typeName) {
1111    if (list.isEmpty() || list.get(0).getPath().contains(".")) {
1112      ElementDefinition ed = new ElementDefinition();
1113      ed.setPath(typeName);
1114      list.add(0, ed);
1115    }
1116    int i = 1; 
1117    while (i < list.size()) { 
1118      String[] pathCurrent = list.get(i).getPath().split("\\."); 
1119      String[] pathLast = list.get(i-1).getPath().split("\\."); 
1120      int firstDiff = 0; // the first entry must be a match 
1121      while (firstDiff < pathCurrent.length && firstDiff < pathLast.length && pathCurrent[firstDiff].equals(pathLast[firstDiff])) { 
1122        firstDiff++; 
1123      } 
1124      if (!(isSibling(pathCurrent, pathLast, firstDiff) || isChild(pathCurrent, pathLast, firstDiff))) { 
1125        // now work backwards down to lastMatch inserting missing path nodes 
1126        ElementDefinition parent = findParent(list, i, list.get(i).getPath()); 
1127        int parentDepth = Utilities.charCount(parent.getPath(), '.')+1; 
1128        int childDepth =  Utilities.charCount(list.get(i).getPath(), '.')+1; 
1129        if (childDepth > parentDepth + 1) { 
1130          String basePath = parent.getPath(); 
1131          String baseId = parent.getId(); 
1132          for (int index = parentDepth; index >= firstDiff; index--) { 
1133            String mtail = makeTail(pathCurrent, parentDepth, index); 
1134            ElementDefinition root = new ElementDefinition().setPath(basePath+"."+mtail); 
1135            root.setId(baseId+"."+mtail); 
1136            list.add(i, root); 
1137          } 
1138        } 
1139      }  
1140      i++; 
1141    } 
1142  } 
1143
1144
1145  private ElementDefinition findParent(List<ElementDefinition> list, int i, String path) { 
1146    while (i > 0 && !path.startsWith(list.get(i).getPath()+".")) { 
1147      i--; 
1148    } 
1149    return list.get(i); 
1150  } 
1151
1152  private boolean isSibling(String[] pathCurrent, String[] pathLast, int firstDiff) { 
1153    return pathCurrent.length == pathLast.length && firstDiff == pathCurrent.length-1; 
1154  } 
1155
1156
1157  private boolean isChild(String[] pathCurrent, String[] pathLast, int firstDiff) { 
1158    return pathCurrent.length == pathLast.length+1 && firstDiff == pathLast.length; 
1159  } 
1160
1161  private String makeTail(String[] pathCurrent, int start, int index) { 
1162    CommaSeparatedStringBuilder b = new CommaSeparatedStringBuilder("."); 
1163    for (int i = start; i <= index; i++) { 
1164      b.append(pathCurrent[i]); 
1165    } 
1166    return b.toString(); 
1167  }
1168
1169  public StructureDefinition trimSnapshot(StructureDefinition profile) {
1170    // first pass: mark elements from the diff
1171    Stack<ElementDefinition> stack = new Stack<ElementDefinition>();
1172    ElementDefinition edRoot = profile.getSnapshot().getElementFirstRep();
1173    if (!edRoot.hasUserData(UserDataNames.SNAPSHOT_FROM_DIFF)) {
1174      stack.push(edRoot);
1175      for (int i = 1; i < profile.getSnapshot().getElement().size(); i++) {
1176        ElementDefinition ed = profile.getSnapshot().getElement().get(i);
1177        String cpath = ed.getPath();
1178        boolean fromDiff = ed.hasUserData(UserDataNames.SNAPSHOT_DERIVATION_DIFF);
1179
1180        String spath = stack.peek().getPath();
1181        while (!(cpath.equals(spath) || cpath.startsWith(spath+"."))) {
1182          stack.pop();
1183          spath = stack.peek().getPath();
1184        }
1185        stack.push(ed);
1186        if (fromDiff) {
1187          for (int j = stack.size() - 1; j >= 0; j--) {
1188            if (stack.get(j).hasUserData(UserDataNames.SNAPSHOT_FROM_DIFF)) {
1189              break;
1190            } else {
1191              stack.get(j).setUserData(UserDataNames.SNAPSHOT_FROM_DIFF, true);
1192            }
1193          }
1194        }
1195      }
1196    }
1197    edRoot.setUserData(UserDataNames.SNAPSHOT_FROM_DIFF, true);
1198
1199    StructureDefinition res = new StructureDefinition();
1200    res.setUrl(profile.getUrl());
1201    res.setVersion(profile.getVersion());
1202    res.setName(profile.getName());
1203    res.setBaseDefinition(profile.getBaseDefinition());
1204    for (ElementDefinition ed : profile.getSnapshot().getElement()) {
1205      if (ed.hasUserData(UserDataNames.SNAPSHOT_FROM_DIFF)) {
1206        res.getSnapshot().getElement().add(ed);
1207      }
1208    }
1209    res.setWebPath(profile.getWebPath());
1210    return res;
1211  } 
1212
1213}